<!DOCTYPE html>
<html lang="en-US">
  <head>
    <meta charset="utf-8">
    <meta name="viewport" content="width=device-width,initial-scale=1">
    <title>动态规划 | AJ</title>
    <meta name="generator" content="VuePress 1.5.0">
    <link rel="shortcut icon" href="/favicon.ico" type="image/x-icon">
    <script>
            var _hmt = _hmt || [];
            (function() {
            var hm = document.createElement("script");
            hm.src = "https://hm.baidu.com/hm.js?51b8c2e72d1adf96524638ce85bb7d72";
            var s = document.getElementsByTagName("script")[0]; 
            s.parentNode.insertBefore(hm, s);

            // 引入谷歌,不需要可删除这段
            var hm1 = document.createElement("script");
            hm1.src = "https://www.googletagmanager.com/gtag/js?id=G-B7351EYS04";
            var s1 = document.getElementsByTagName("script")[0]; 
            s1.parentNode.insertBefore(hm1, s1);
            })();

            // 谷歌加载,不需要可删除
            window.dataLayer = window.dataLayer || [];
            function gtag(){dataLayer.push(arguments);}
            gtag('js', new Date());

            gtag('config', 'G-B7351EYS04');
        </script>
    <meta name="description" content="阿俊博客|记录一个程序员的成长历程 阿俊博客(blog.zhequtao.com)记录一个后端程序员的成长历程,分享他的学习笔记和心得,还有些开发必备技巧哦! java golang web html dev开发">
    <link rel="preload" href="/assets/css/0.styles.a3df589e.css" as="style"><link rel="preload" href="/assets/js/app.cb35c8f6.js" as="script"><link rel="preload" href="/assets/js/2.063846a6.js" as="script"><link rel="preload" href="/assets/js/4.1ffb4609.js" as="script"><link rel="preload" href="/assets/js/575.b0d429a1.js" as="script"><link rel="prefetch" href="/assets/js/10.5629fe4d.js"><link rel="prefetch" href="/assets/js/100.8417ccea.js"><link rel="prefetch" href="/assets/js/101.37fdb377.js"><link rel="prefetch" href="/assets/js/102.848b686d.js"><link rel="prefetch" href="/assets/js/103.6a2489a0.js"><link rel="prefetch" href="/assets/js/104.99e8899f.js"><link rel="prefetch" href="/assets/js/105.8b741763.js"><link rel="prefetch" href="/assets/js/106.08163715.js"><link rel="prefetch" href="/assets/js/107.21801349.js"><link rel="prefetch" href="/assets/js/108.e3a2892b.js"><link rel="prefetch" href="/assets/js/109.dab5618c.js"><link rel="prefetch" href="/assets/js/11.cddc1623.js"><link rel="prefetch" href="/assets/js/110.f5249b39.js"><link rel="prefetch" href="/assets/js/111.9abf8bce.js"><link rel="prefetch" href="/assets/js/112.8eb86924.js"><link rel="prefetch" href="/assets/js/113.c180ed46.js"><link rel="prefetch" href="/assets/js/114.2370f5b5.js"><link rel="prefetch" href="/assets/js/115.88dc3fd8.js"><link rel="prefetch" href="/assets/js/116.63403600.js"><link rel="prefetch" href="/assets/js/117.83674aa0.js"><link rel="prefetch" href="/assets/js/118.9c58c685.js"><link rel="prefetch" href="/assets/js/119.621f9a70.js"><link rel="prefetch" href="/assets/js/12.ff3d03f5.js"><link rel="prefetch" href="/assets/js/120.a6d2b7f7.js"><link rel="prefetch" href="/assets/js/121.ae0ce9d1.js"><link rel="prefetch" href="/assets/js/122.de240e6d.js"><link rel="prefetch" href="/assets/js/123.b043e3e4.js"><link rel="prefetch" href="/assets/js/124.550af937.js"><link rel="prefetch" href="/assets/js/125.6f06b34c.js"><link rel="prefetch" href="/assets/js/126.38d64604.js"><link rel="prefetch" href="/assets/js/127.a948db56.js"><link rel="prefetch" href="/assets/js/128.4ca789e0.js"><link rel="prefetch" href="/assets/js/129.59be4505.js"><link rel="prefetch" href="/assets/js/13.e9f75cc3.js"><link rel="prefetch" href="/assets/js/130.ddae76a9.js"><link rel="prefetch" href="/assets/js/131.d969c265.js"><link rel="prefetch" href="/assets/js/132.5f43ce5c.js"><link rel="prefetch" href="/assets/js/133.b651af22.js"><link rel="prefetch" href="/assets/js/134.2499236a.js"><link rel="prefetch" href="/assets/js/135.4180596c.js"><link rel="prefetch" href="/assets/js/136.2c309233.js"><link rel="prefetch" href="/assets/js/137.72ca42dd.js"><link rel="prefetch" href="/assets/js/138.3772cd38.js"><link rel="prefetch" href="/assets/js/139.1d0a53da.js"><link rel="prefetch" href="/assets/js/14.be4b89ed.js"><link rel="prefetch" href="/assets/js/140.22368353.js"><link rel="prefetch" href="/assets/js/141.a14aef3c.js"><link rel="prefetch" href="/assets/js/142.2041ce3a.js"><link rel="prefetch" href="/assets/js/143.377262ec.js"><link rel="prefetch" href="/assets/js/144.8fcbc368.js"><link rel="prefetch" href="/assets/js/145.46da36bf.js"><link rel="prefetch" href="/assets/js/146.eceae0d9.js"><link rel="prefetch" href="/assets/js/147.e1bd6531.js"><link rel="prefetch" href="/assets/js/148.76f193ce.js"><link rel="prefetch" href="/assets/js/149.587bd581.js"><link rel="prefetch" href="/assets/js/15.e3219ac0.js"><link rel="prefetch" href="/assets/js/150.169c71e0.js"><link rel="prefetch" href="/assets/js/151.384021ea.js"><link rel="prefetch" href="/assets/js/152.0f20cf03.js"><link rel="prefetch" href="/assets/js/153.fd94af1e.js"><link rel="prefetch" href="/assets/js/154.a550f5dc.js"><link rel="prefetch" href="/assets/js/155.ba1ae86e.js"><link rel="prefetch" href="/assets/js/156.3b98ded0.js"><link rel="prefetch" href="/assets/js/157.cd378596.js"><link rel="prefetch" href="/assets/js/158.c138d0df.js"><link rel="prefetch" href="/assets/js/159.2635f7f4.js"><link rel="prefetch" href="/assets/js/16.c9c35d42.js"><link rel="prefetch" href="/assets/js/160.d51b4126.js"><link rel="prefetch" href="/assets/js/161.5dc29e7b.js"><link rel="prefetch" href="/assets/js/162.f257a92b.js"><link rel="prefetch" href="/assets/js/163.9eb75e40.js"><link rel="prefetch" href="/assets/js/164.8fb1e22b.js"><link rel="prefetch" href="/assets/js/165.49255503.js"><link rel="prefetch" href="/assets/js/166.e54539e6.js"><link rel="prefetch" href="/assets/js/167.a06acdb0.js"><link rel="prefetch" href="/assets/js/168.948ab620.js"><link rel="prefetch" href="/assets/js/169.7d756812.js"><link rel="prefetch" href="/assets/js/17.81067bc8.js"><link rel="prefetch" href="/assets/js/170.ffe63330.js"><link rel="prefetch" href="/assets/js/171.835398b9.js"><link rel="prefetch" href="/assets/js/172.3987be39.js"><link rel="prefetch" href="/assets/js/173.e3cedb8a.js"><link rel="prefetch" href="/assets/js/174.11a32588.js"><link rel="prefetch" href="/assets/js/175.da6f9782.js"><link rel="prefetch" href="/assets/js/176.50e55edc.js"><link rel="prefetch" href="/assets/js/177.a89a1d17.js"><link rel="prefetch" href="/assets/js/178.7ad3ce84.js"><link rel="prefetch" href="/assets/js/179.98a1343b.js"><link rel="prefetch" href="/assets/js/18.b67caf4c.js"><link rel="prefetch" href="/assets/js/180.4e98599b.js"><link rel="prefetch" href="/assets/js/181.dd885afd.js"><link rel="prefetch" href="/assets/js/182.789990c8.js"><link rel="prefetch" href="/assets/js/183.f11ca2fd.js"><link rel="prefetch" href="/assets/js/184.fcf128ec.js"><link rel="prefetch" href="/assets/js/185.54e1e9b6.js"><link rel="prefetch" href="/assets/js/186.db91021a.js"><link rel="prefetch" href="/assets/js/187.5309dd42.js"><link rel="prefetch" href="/assets/js/188.615821ea.js"><link rel="prefetch" href="/assets/js/189.f23f1d42.js"><link rel="prefetch" href="/assets/js/19.294a011c.js"><link rel="prefetch" href="/assets/js/190.efe894bc.js"><link rel="prefetch" href="/assets/js/191.0d14904a.js"><link rel="prefetch" href="/assets/js/192.efd25a9e.js"><link rel="prefetch" href="/assets/js/193.88151f34.js"><link rel="prefetch" href="/assets/js/194.efedce14.js"><link rel="prefetch" href="/assets/js/195.03ac15bb.js"><link rel="prefetch" href="/assets/js/196.fbc18389.js"><link rel="prefetch" href="/assets/js/197.0257ab5e.js"><link rel="prefetch" href="/assets/js/198.f1de2817.js"><link rel="prefetch" href="/assets/js/199.8f1c166b.js"><link rel="prefetch" href="/assets/js/20.1a41edb1.js"><link rel="prefetch" href="/assets/js/200.4af99727.js"><link rel="prefetch" href="/assets/js/201.9f8caef1.js"><link rel="prefetch" href="/assets/js/202.6f07d705.js"><link rel="prefetch" href="/assets/js/203.5012fe50.js"><link rel="prefetch" href="/assets/js/204.3a0dfd8e.js"><link rel="prefetch" href="/assets/js/205.0ba9b606.js"><link rel="prefetch" href="/assets/js/206.663a49ec.js"><link rel="prefetch" href="/assets/js/207.b2406149.js"><link rel="prefetch" href="/assets/js/208.b0b2dfd8.js"><link rel="prefetch" href="/assets/js/209.41a0ec9f.js"><link rel="prefetch" href="/assets/js/21.b6ea6f9a.js"><link rel="prefetch" href="/assets/js/210.6f36beb8.js"><link rel="prefetch" href="/assets/js/211.90ef6e5c.js"><link rel="prefetch" href="/assets/js/212.42339063.js"><link rel="prefetch" href="/assets/js/213.a2bfeda9.js"><link rel="prefetch" href="/assets/js/214.5c7eb42a.js"><link rel="prefetch" href="/assets/js/215.18260ae5.js"><link rel="prefetch" href="/assets/js/216.7678fd29.js"><link rel="prefetch" href="/assets/js/217.9d936f88.js"><link rel="prefetch" href="/assets/js/218.bac403c4.js"><link rel="prefetch" href="/assets/js/219.9d8cb16b.js"><link rel="prefetch" href="/assets/js/22.367cc253.js"><link rel="prefetch" href="/assets/js/220.375b7707.js"><link rel="prefetch" href="/assets/js/221.3e400da4.js"><link rel="prefetch" href="/assets/js/222.8fbd2857.js"><link rel="prefetch" href="/assets/js/223.76a10075.js"><link rel="prefetch" href="/assets/js/224.ff94cc4e.js"><link rel="prefetch" href="/assets/js/225.d4688ca6.js"><link rel="prefetch" href="/assets/js/226.b13b18af.js"><link rel="prefetch" href="/assets/js/227.288d0f96.js"><link rel="prefetch" href="/assets/js/228.60430ac0.js"><link rel="prefetch" href="/assets/js/229.da728342.js"><link rel="prefetch" href="/assets/js/23.bc3de730.js"><link rel="prefetch" href="/assets/js/230.d8417d20.js"><link rel="prefetch" href="/assets/js/231.6a9ce0b4.js"><link rel="prefetch" href="/assets/js/232.7611b413.js"><link rel="prefetch" href="/assets/js/233.94712cf9.js"><link rel="prefetch" href="/assets/js/234.93888298.js"><link rel="prefetch" href="/assets/js/235.62506981.js"><link rel="prefetch" href="/assets/js/236.5a055c7c.js"><link rel="prefetch" href="/assets/js/237.0a6c4902.js"><link rel="prefetch" href="/assets/js/238.e5f37663.js"><link rel="prefetch" href="/assets/js/239.331bba86.js"><link rel="prefetch" href="/assets/js/24.82f0901c.js"><link rel="prefetch" href="/assets/js/240.59591cfc.js"><link rel="prefetch" href="/assets/js/241.ce671f47.js"><link rel="prefetch" href="/assets/js/242.fb2542fa.js"><link rel="prefetch" href="/assets/js/243.74abc73d.js"><link rel="prefetch" href="/assets/js/244.ecd707b2.js"><link rel="prefetch" href="/assets/js/245.d728367b.js"><link rel="prefetch" href="/assets/js/246.9270e7fe.js"><link rel="prefetch" href="/assets/js/247.a421ba15.js"><link rel="prefetch" href="/assets/js/248.e759132e.js"><link rel="prefetch" href="/assets/js/249.3077fb46.js"><link rel="prefetch" href="/assets/js/25.95c551dc.js"><link rel="prefetch" href="/assets/js/250.5fe4dd03.js"><link rel="prefetch" href="/assets/js/251.4b8fe76c.js"><link rel="prefetch" href="/assets/js/252.0d1cf7ea.js"><link rel="prefetch" href="/assets/js/253.89d16ba0.js"><link rel="prefetch" href="/assets/js/254.8d1afc68.js"><link rel="prefetch" href="/assets/js/255.64e680cb.js"><link rel="prefetch" href="/assets/js/256.9defbd0e.js"><link rel="prefetch" href="/assets/js/257.1fef24fd.js"><link rel="prefetch" href="/assets/js/258.4e205286.js"><link rel="prefetch" href="/assets/js/259.f3d56efc.js"><link rel="prefetch" href="/assets/js/26.7fe56bac.js"><link rel="prefetch" href="/assets/js/260.378299e6.js"><link rel="prefetch" href="/assets/js/261.8e4fb397.js"><link rel="prefetch" href="/assets/js/262.54595d98.js"><link rel="prefetch" href="/assets/js/263.fb333dc1.js"><link rel="prefetch" href="/assets/js/264.13d13301.js"><link rel="prefetch" href="/assets/js/265.c85104bc.js"><link rel="prefetch" href="/assets/js/266.9f3d1f1c.js"><link rel="prefetch" href="/assets/js/267.fb392815.js"><link rel="prefetch" href="/assets/js/268.add7eacb.js"><link rel="prefetch" href="/assets/js/269.7e49fcc7.js"><link rel="prefetch" href="/assets/js/27.5547e5f0.js"><link rel="prefetch" href="/assets/js/270.22342070.js"><link rel="prefetch" href="/assets/js/271.59917b1a.js"><link rel="prefetch" href="/assets/js/272.4a4751d5.js"><link rel="prefetch" href="/assets/js/273.f4c2fa5c.js"><link rel="prefetch" href="/assets/js/274.1208bc94.js"><link rel="prefetch" href="/assets/js/275.f6528753.js"><link rel="prefetch" href="/assets/js/276.a68772cd.js"><link rel="prefetch" href="/assets/js/277.f154ab32.js"><link rel="prefetch" href="/assets/js/278.bb616a63.js"><link rel="prefetch" href="/assets/js/279.6a356cff.js"><link rel="prefetch" href="/assets/js/28.b08b2847.js"><link rel="prefetch" href="/assets/js/280.5afc20fc.js"><link rel="prefetch" href="/assets/js/281.3cd86225.js"><link rel="prefetch" href="/assets/js/282.3ecb92aa.js"><link rel="prefetch" href="/assets/js/283.85159ea7.js"><link rel="prefetch" href="/assets/js/284.b6545c68.js"><link rel="prefetch" href="/assets/js/285.5e83ee29.js"><link rel="prefetch" href="/assets/js/286.2aad298d.js"><link rel="prefetch" href="/assets/js/287.3ca76244.js"><link rel="prefetch" href="/assets/js/288.5b17963d.js"><link rel="prefetch" href="/assets/js/289.f47a759b.js"><link rel="prefetch" href="/assets/js/29.562dbf7d.js"><link rel="prefetch" href="/assets/js/290.36b603c7.js"><link rel="prefetch" href="/assets/js/291.a9bd8951.js"><link rel="prefetch" href="/assets/js/292.dfc54f28.js"><link rel="prefetch" href="/assets/js/293.2d061212.js"><link rel="prefetch" href="/assets/js/294.6d564a9e.js"><link rel="prefetch" href="/assets/js/295.a31dd593.js"><link rel="prefetch" href="/assets/js/296.3101e5e8.js"><link rel="prefetch" href="/assets/js/297.7efde936.js"><link rel="prefetch" href="/assets/js/298.8bb3aa68.js"><link rel="prefetch" href="/assets/js/299.8b51e6bd.js"><link rel="prefetch" href="/assets/js/3.76257eb7.js"><link rel="prefetch" href="/assets/js/30.221adea2.js"><link rel="prefetch" href="/assets/js/300.62effe45.js"><link rel="prefetch" href="/assets/js/301.98c863c5.js"><link rel="prefetch" href="/assets/js/302.e3493ab2.js"><link rel="prefetch" href="/assets/js/303.800c8028.js"><link rel="prefetch" href="/assets/js/304.b6f08986.js"><link rel="prefetch" href="/assets/js/305.09af356b.js"><link rel="prefetch" href="/assets/js/306.d0d3589d.js"><link rel="prefetch" href="/assets/js/307.ee2fd249.js"><link rel="prefetch" href="/assets/js/308.f3f76368.js"><link rel="prefetch" href="/assets/js/309.d2b5ce40.js"><link rel="prefetch" href="/assets/js/31.334fc8bb.js"><link rel="prefetch" href="/assets/js/310.b4fa2feb.js"><link rel="prefetch" href="/assets/js/311.7d747ef3.js"><link rel="prefetch" href="/assets/js/312.89bdff40.js"><link rel="prefetch" href="/assets/js/313.875b82fe.js"><link rel="prefetch" href="/assets/js/314.0bbe51c4.js"><link rel="prefetch" href="/assets/js/315.cc07dbcf.js"><link rel="prefetch" href="/assets/js/316.bc72b152.js"><link rel="prefetch" href="/assets/js/317.55462812.js"><link rel="prefetch" href="/assets/js/318.a158fda0.js"><link rel="prefetch" href="/assets/js/319.b03a5bd2.js"><link rel="prefetch" href="/assets/js/32.d6826b16.js"><link rel="prefetch" href="/assets/js/320.a5bd19b0.js"><link rel="prefetch" href="/assets/js/321.4f9faaa7.js"><link rel="prefetch" href="/assets/js/322.dbd3b4fa.js"><link rel="prefetch" href="/assets/js/323.a04e2062.js"><link rel="prefetch" href="/assets/js/324.c45b46cf.js"><link rel="prefetch" href="/assets/js/325.cd1460c4.js"><link rel="prefetch" href="/assets/js/326.bd90ef85.js"><link rel="prefetch" href="/assets/js/327.8bf38ef7.js"><link rel="prefetch" href="/assets/js/328.99e9aed3.js"><link rel="prefetch" href="/assets/js/329.de0012cb.js"><link rel="prefetch" href="/assets/js/33.b1059062.js"><link rel="prefetch" href="/assets/js/330.59f11391.js"><link rel="prefetch" href="/assets/js/331.6d16a13c.js"><link rel="prefetch" href="/assets/js/332.922ca235.js"><link rel="prefetch" href="/assets/js/333.c94c3602.js"><link rel="prefetch" href="/assets/js/334.77e02010.js"><link rel="prefetch" href="/assets/js/335.1e0c4f7b.js"><link rel="prefetch" href="/assets/js/336.5675dc4f.js"><link rel="prefetch" href="/assets/js/337.bb6e11dc.js"><link rel="prefetch" href="/assets/js/338.294981e9.js"><link rel="prefetch" href="/assets/js/339.d0376372.js"><link rel="prefetch" href="/assets/js/34.0c7d5782.js"><link rel="prefetch" href="/assets/js/340.64596428.js"><link rel="prefetch" href="/assets/js/341.ec0f9409.js"><link rel="prefetch" href="/assets/js/342.7abc47c4.js"><link rel="prefetch" href="/assets/js/343.4262d486.js"><link rel="prefetch" href="/assets/js/344.8729ad8c.js"><link rel="prefetch" href="/assets/js/345.c210d888.js"><link rel="prefetch" href="/assets/js/346.6f42f7cb.js"><link rel="prefetch" href="/assets/js/347.81b41ae5.js"><link rel="prefetch" href="/assets/js/348.07eca37c.js"><link rel="prefetch" href="/assets/js/349.8019d6f3.js"><link rel="prefetch" href="/assets/js/35.ae14e37f.js"><link rel="prefetch" href="/assets/js/350.57da2e7b.js"><link rel="prefetch" href="/assets/js/351.2e99afdf.js"><link rel="prefetch" href="/assets/js/352.67dd88b7.js"><link rel="prefetch" href="/assets/js/353.15b9f624.js"><link rel="prefetch" href="/assets/js/354.a63e8432.js"><link rel="prefetch" href="/assets/js/355.bbc16ee9.js"><link rel="prefetch" href="/assets/js/356.ff63d3bb.js"><link rel="prefetch" href="/assets/js/357.4fb2d941.js"><link rel="prefetch" href="/assets/js/358.55182977.js"><link rel="prefetch" href="/assets/js/359.265c3d26.js"><link rel="prefetch" href="/assets/js/36.b9ed4cf1.js"><link rel="prefetch" href="/assets/js/360.ced80eb3.js"><link rel="prefetch" href="/assets/js/361.afe6ba84.js"><link rel="prefetch" href="/assets/js/362.c2b62518.js"><link rel="prefetch" href="/assets/js/363.0c4a4800.js"><link rel="prefetch" href="/assets/js/364.ce60291b.js"><link rel="prefetch" href="/assets/js/365.0e3a61f9.js"><link rel="prefetch" href="/assets/js/366.d53ccb03.js"><link rel="prefetch" href="/assets/js/367.689e464d.js"><link rel="prefetch" href="/assets/js/368.418c571f.js"><link rel="prefetch" href="/assets/js/369.c2fff3c8.js"><link rel="prefetch" href="/assets/js/37.a021ac57.js"><link rel="prefetch" href="/assets/js/370.a932b958.js"><link rel="prefetch" href="/assets/js/371.7d153241.js"><link rel="prefetch" href="/assets/js/372.fb9878fa.js"><link rel="prefetch" href="/assets/js/373.85772e03.js"><link rel="prefetch" href="/assets/js/374.b4a8b1b6.js"><link rel="prefetch" href="/assets/js/375.32f70596.js"><link rel="prefetch" href="/assets/js/376.a16d79a8.js"><link rel="prefetch" href="/assets/js/377.c996b7e1.js"><link rel="prefetch" href="/assets/js/378.d37d15c7.js"><link rel="prefetch" href="/assets/js/379.b81ba7dd.js"><link rel="prefetch" href="/assets/js/38.89138658.js"><link rel="prefetch" href="/assets/js/380.524c9b31.js"><link rel="prefetch" href="/assets/js/381.7ebfd6db.js"><link rel="prefetch" href="/assets/js/382.29edda0f.js"><link rel="prefetch" href="/assets/js/383.9642a212.js"><link rel="prefetch" href="/assets/js/384.086e3b42.js"><link rel="prefetch" href="/assets/js/385.a9bb46a8.js"><link rel="prefetch" href="/assets/js/386.f2561a39.js"><link rel="prefetch" href="/assets/js/387.ba9b6aaa.js"><link rel="prefetch" href="/assets/js/388.e0ace495.js"><link rel="prefetch" href="/assets/js/389.ba8c09dd.js"><link rel="prefetch" href="/assets/js/39.04f331e3.js"><link rel="prefetch" href="/assets/js/390.de1bb48b.js"><link rel="prefetch" href="/assets/js/391.7cc6edeb.js"><link rel="prefetch" href="/assets/js/392.0493a6f7.js"><link rel="prefetch" href="/assets/js/393.ba2d3e62.js"><link rel="prefetch" href="/assets/js/394.b3aa9224.js"><link rel="prefetch" href="/assets/js/395.f4df3a60.js"><link rel="prefetch" href="/assets/js/396.09644790.js"><link rel="prefetch" href="/assets/js/397.76163964.js"><link rel="prefetch" href="/assets/js/398.377fd8fc.js"><link rel="prefetch" href="/assets/js/399.39059be5.js"><link rel="prefetch" href="/assets/js/40.a21abf05.js"><link rel="prefetch" href="/assets/js/400.559a547f.js"><link rel="prefetch" href="/assets/js/401.bc6d738c.js"><link rel="prefetch" href="/assets/js/402.c504ed7b.js"><link rel="prefetch" href="/assets/js/403.77a0af9c.js"><link rel="prefetch" href="/assets/js/404.0f408cc6.js"><link rel="prefetch" href="/assets/js/405.90b0bab6.js"><link rel="prefetch" href="/assets/js/406.01b11432.js"><link rel="prefetch" href="/assets/js/407.58991ce5.js"><link rel="prefetch" href="/assets/js/408.9806278e.js"><link rel="prefetch" href="/assets/js/409.8d9b4bb3.js"><link rel="prefetch" href="/assets/js/41.6bcfc592.js"><link rel="prefetch" href="/assets/js/410.02dee620.js"><link rel="prefetch" href="/assets/js/411.3d12d3a6.js"><link rel="prefetch" href="/assets/js/412.37a62624.js"><link rel="prefetch" href="/assets/js/413.bda7ca34.js"><link rel="prefetch" href="/assets/js/414.2abb6547.js"><link rel="prefetch" href="/assets/js/415.1d271923.js"><link rel="prefetch" href="/assets/js/416.d1b11dfe.js"><link rel="prefetch" href="/assets/js/417.fcbf07ff.js"><link rel="prefetch" href="/assets/js/418.524d40ba.js"><link rel="prefetch" href="/assets/js/419.f264e463.js"><link rel="prefetch" href="/assets/js/42.ec85a270.js"><link rel="prefetch" href="/assets/js/420.8b99e60d.js"><link rel="prefetch" href="/assets/js/421.c697d876.js"><link rel="prefetch" href="/assets/js/422.4af54ae0.js"><link rel="prefetch" href="/assets/js/423.b75f24ff.js"><link rel="prefetch" href="/assets/js/424.ea80054f.js"><link rel="prefetch" href="/assets/js/425.804b48b0.js"><link rel="prefetch" href="/assets/js/426.ffed8383.js"><link rel="prefetch" href="/assets/js/427.2040bd22.js"><link rel="prefetch" href="/assets/js/428.b878fb56.js"><link rel="prefetch" href="/assets/js/429.f81fd922.js"><link rel="prefetch" href="/assets/js/43.c174449d.js"><link rel="prefetch" href="/assets/js/430.16f328ab.js"><link rel="prefetch" href="/assets/js/431.56f11924.js"><link rel="prefetch" href="/assets/js/432.e4c77710.js"><link rel="prefetch" href="/assets/js/433.29acf14b.js"><link rel="prefetch" href="/assets/js/434.33ee22fc.js"><link rel="prefetch" href="/assets/js/435.516f7600.js"><link rel="prefetch" href="/assets/js/436.28ae526a.js"><link rel="prefetch" href="/assets/js/437.b9bac473.js"><link rel="prefetch" href="/assets/js/438.711bd934.js"><link rel="prefetch" href="/assets/js/439.fe5f28bd.js"><link rel="prefetch" href="/assets/js/44.8704338b.js"><link rel="prefetch" href="/assets/js/440.b2f48747.js"><link rel="prefetch" href="/assets/js/441.4862a724.js"><link rel="prefetch" href="/assets/js/442.751f8ae7.js"><link rel="prefetch" href="/assets/js/443.9998dbe9.js"><link rel="prefetch" href="/assets/js/444.23d3f688.js"><link rel="prefetch" href="/assets/js/445.72419f35.js"><link rel="prefetch" href="/assets/js/446.21e02b7b.js"><link rel="prefetch" href="/assets/js/447.6bd039e5.js"><link rel="prefetch" href="/assets/js/448.af29ff31.js"><link rel="prefetch" href="/assets/js/449.bbdca196.js"><link rel="prefetch" href="/assets/js/45.f8a2a3b3.js"><link rel="prefetch" href="/assets/js/450.32e470b8.js"><link rel="prefetch" href="/assets/js/451.f4c8ff6a.js"><link rel="prefetch" href="/assets/js/452.c0ec8943.js"><link rel="prefetch" href="/assets/js/453.5af475c6.js"><link rel="prefetch" href="/assets/js/454.567aa6c1.js"><link rel="prefetch" href="/assets/js/455.326072d1.js"><link rel="prefetch" href="/assets/js/456.64b88847.js"><link rel="prefetch" href="/assets/js/457.61c91559.js"><link rel="prefetch" href="/assets/js/458.4f4d43d6.js"><link rel="prefetch" href="/assets/js/459.a88891cb.js"><link rel="prefetch" href="/assets/js/46.90855a0f.js"><link rel="prefetch" href="/assets/js/460.fb9e15f6.js"><link rel="prefetch" href="/assets/js/461.998a4991.js"><link rel="prefetch" href="/assets/js/462.56ecfb03.js"><link rel="prefetch" href="/assets/js/463.582cd053.js"><link rel="prefetch" href="/assets/js/464.f12a0050.js"><link rel="prefetch" href="/assets/js/465.cc3b08a8.js"><link rel="prefetch" href="/assets/js/466.ea7e4ce2.js"><link rel="prefetch" href="/assets/js/467.58700d93.js"><link rel="prefetch" href="/assets/js/468.bb9998cd.js"><link rel="prefetch" href="/assets/js/469.232d261d.js"><link rel="prefetch" href="/assets/js/47.02516d33.js"><link rel="prefetch" href="/assets/js/470.90ab2be8.js"><link rel="prefetch" href="/assets/js/471.3652fec6.js"><link rel="prefetch" href="/assets/js/472.bc7517c9.js"><link rel="prefetch" href="/assets/js/473.27b7892f.js"><link rel="prefetch" href="/assets/js/474.0d488768.js"><link rel="prefetch" href="/assets/js/475.bc33cf17.js"><link rel="prefetch" href="/assets/js/476.76ce67eb.js"><link rel="prefetch" href="/assets/js/477.a20657f6.js"><link rel="prefetch" href="/assets/js/478.8905ef26.js"><link rel="prefetch" href="/assets/js/479.23ec3dc9.js"><link rel="prefetch" href="/assets/js/48.8d38983c.js"><link rel="prefetch" href="/assets/js/480.105bf58e.js"><link rel="prefetch" href="/assets/js/481.d62a3699.js"><link rel="prefetch" href="/assets/js/482.6cb10cdb.js"><link rel="prefetch" href="/assets/js/483.15b9ef53.js"><link rel="prefetch" href="/assets/js/484.794aff9c.js"><link rel="prefetch" href="/assets/js/485.3e6ef3cb.js"><link rel="prefetch" href="/assets/js/486.fc20eb22.js"><link rel="prefetch" href="/assets/js/487.2a4f7d47.js"><link rel="prefetch" href="/assets/js/488.24ba9af5.js"><link rel="prefetch" href="/assets/js/489.d451928e.js"><link rel="prefetch" href="/assets/js/49.bd70c59c.js"><link rel="prefetch" href="/assets/js/490.d83e4fc7.js"><link rel="prefetch" href="/assets/js/491.0210a738.js"><link rel="prefetch" href="/assets/js/492.3a69cd85.js"><link rel="prefetch" href="/assets/js/493.89d2920f.js"><link rel="prefetch" href="/assets/js/494.b7d1c15e.js"><link rel="prefetch" href="/assets/js/495.7ccfe17f.js"><link rel="prefetch" href="/assets/js/496.0d6c912a.js"><link rel="prefetch" href="/assets/js/497.087ca2c6.js"><link rel="prefetch" href="/assets/js/498.f2b3c894.js"><link rel="prefetch" href="/assets/js/499.e741f312.js"><link rel="prefetch" href="/assets/js/5.405f2620.js"><link rel="prefetch" href="/assets/js/50.9df07553.js"><link rel="prefetch" href="/assets/js/500.cb9babb9.js"><link rel="prefetch" href="/assets/js/501.63a859b6.js"><link rel="prefetch" href="/assets/js/502.f346b273.js"><link rel="prefetch" href="/assets/js/503.cdcd3de3.js"><link rel="prefetch" href="/assets/js/504.e83ec450.js"><link rel="prefetch" href="/assets/js/505.95f18293.js"><link rel="prefetch" href="/assets/js/506.02060a3c.js"><link rel="prefetch" href="/assets/js/507.859d6ae4.js"><link rel="prefetch" href="/assets/js/508.9724d886.js"><link rel="prefetch" href="/assets/js/509.e17dd53e.js"><link rel="prefetch" href="/assets/js/51.3dfc6350.js"><link rel="prefetch" href="/assets/js/510.ea0c942f.js"><link rel="prefetch" href="/assets/js/511.64a7f9a8.js"><link rel="prefetch" href="/assets/js/512.6cce418a.js"><link rel="prefetch" href="/assets/js/513.ea813fe8.js"><link rel="prefetch" href="/assets/js/514.10242470.js"><link rel="prefetch" href="/assets/js/515.5308bdf6.js"><link rel="prefetch" href="/assets/js/516.dfb113bc.js"><link rel="prefetch" href="/assets/js/517.96c71069.js"><link rel="prefetch" href="/assets/js/518.5594480e.js"><link rel="prefetch" href="/assets/js/519.91e848ae.js"><link rel="prefetch" href="/assets/js/52.dd230cd7.js"><link rel="prefetch" href="/assets/js/520.ebe69ce9.js"><link rel="prefetch" href="/assets/js/521.92b80342.js"><link rel="prefetch" href="/assets/js/522.6ce581ea.js"><link rel="prefetch" href="/assets/js/523.40b7f2f9.js"><link rel="prefetch" href="/assets/js/524.4ef256d3.js"><link rel="prefetch" href="/assets/js/525.19741e4a.js"><link rel="prefetch" href="/assets/js/526.e5de1675.js"><link rel="prefetch" href="/assets/js/527.9a79cd42.js"><link rel="prefetch" href="/assets/js/528.72732eb8.js"><link rel="prefetch" href="/assets/js/529.2ea03e45.js"><link rel="prefetch" href="/assets/js/53.a349c565.js"><link rel="prefetch" href="/assets/js/530.5d1103e7.js"><link rel="prefetch" href="/assets/js/531.82b032d6.js"><link rel="prefetch" href="/assets/js/532.12ee4beb.js"><link rel="prefetch" href="/assets/js/533.db9a90f7.js"><link rel="prefetch" href="/assets/js/534.fe139db4.js"><link rel="prefetch" href="/assets/js/535.056a6fbb.js"><link rel="prefetch" href="/assets/js/536.6bf85c15.js"><link rel="prefetch" href="/assets/js/537.6e2e1ccf.js"><link rel="prefetch" href="/assets/js/538.54eddb3b.js"><link rel="prefetch" href="/assets/js/539.6f00a207.js"><link rel="prefetch" href="/assets/js/54.e292b52f.js"><link rel="prefetch" href="/assets/js/540.9c956205.js"><link rel="prefetch" href="/assets/js/541.50f41228.js"><link rel="prefetch" href="/assets/js/542.a2b1879e.js"><link rel="prefetch" href="/assets/js/543.4e5e17c9.js"><link rel="prefetch" href="/assets/js/544.63d85227.js"><link rel="prefetch" href="/assets/js/545.c3923644.js"><link rel="prefetch" href="/assets/js/546.e64ad073.js"><link rel="prefetch" href="/assets/js/547.35a8752d.js"><link rel="prefetch" href="/assets/js/548.b62a1348.js"><link rel="prefetch" href="/assets/js/549.369e2ea0.js"><link rel="prefetch" href="/assets/js/55.21bb2983.js"><link rel="prefetch" href="/assets/js/550.b4632248.js"><link rel="prefetch" href="/assets/js/551.18f1879c.js"><link rel="prefetch" href="/assets/js/552.162e63cd.js"><link rel="prefetch" href="/assets/js/553.6998130e.js"><link rel="prefetch" href="/assets/js/554.89126c3d.js"><link rel="prefetch" href="/assets/js/555.a5f63b8a.js"><link rel="prefetch" href="/assets/js/556.35381cef.js"><link rel="prefetch" href="/assets/js/557.ceeecf52.js"><link rel="prefetch" href="/assets/js/558.253e6e4f.js"><link rel="prefetch" href="/assets/js/559.5cfbb773.js"><link rel="prefetch" href="/assets/js/56.5382d6b4.js"><link rel="prefetch" href="/assets/js/560.cca52f22.js"><link rel="prefetch" href="/assets/js/561.ea8d1141.js"><link rel="prefetch" href="/assets/js/562.c32e7b96.js"><link rel="prefetch" href="/assets/js/563.9bdd42e7.js"><link rel="prefetch" href="/assets/js/564.b3b87ec0.js"><link rel="prefetch" href="/assets/js/565.4be0d0f7.js"><link rel="prefetch" href="/assets/js/566.9f379d12.js"><link rel="prefetch" href="/assets/js/567.261e3181.js"><link rel="prefetch" href="/assets/js/568.4229e365.js"><link rel="prefetch" href="/assets/js/569.e662c167.js"><link rel="prefetch" href="/assets/js/57.8129f7e0.js"><link rel="prefetch" href="/assets/js/570.97ff6423.js"><link rel="prefetch" href="/assets/js/571.de1377cd.js"><link rel="prefetch" href="/assets/js/572.48b8400b.js"><link rel="prefetch" href="/assets/js/573.8251ebaf.js"><link rel="prefetch" href="/assets/js/574.ec3d6c1e.js"><link rel="prefetch" href="/assets/js/576.98ce9170.js"><link rel="prefetch" href="/assets/js/577.85fc2017.js"><link rel="prefetch" href="/assets/js/578.1393ac7f.js"><link rel="prefetch" href="/assets/js/579.1340e178.js"><link rel="prefetch" href="/assets/js/58.85ac2740.js"><link rel="prefetch" href="/assets/js/580.a5979445.js"><link rel="prefetch" href="/assets/js/581.effdc269.js"><link rel="prefetch" href="/assets/js/582.13276063.js"><link rel="prefetch" href="/assets/js/583.357a2443.js"><link rel="prefetch" href="/assets/js/584.338ef731.js"><link rel="prefetch" href="/assets/js/585.87932741.js"><link rel="prefetch" href="/assets/js/586.b1d6e000.js"><link rel="prefetch" href="/assets/js/587.ed5b8377.js"><link rel="prefetch" href="/assets/js/588.16d2c418.js"><link rel="prefetch" href="/assets/js/589.c96fd7fa.js"><link rel="prefetch" href="/assets/js/59.0b225757.js"><link rel="prefetch" href="/assets/js/590.1a06b2a0.js"><link rel="prefetch" href="/assets/js/591.0efd886c.js"><link rel="prefetch" href="/assets/js/592.b22d0ef5.js"><link rel="prefetch" href="/assets/js/593.84ed6ebe.js"><link rel="prefetch" href="/assets/js/594.cd721b88.js"><link rel="prefetch" href="/assets/js/595.2400817a.js"><link rel="prefetch" href="/assets/js/596.f2c512d1.js"><link rel="prefetch" href="/assets/js/597.df10ec57.js"><link rel="prefetch" href="/assets/js/598.61ef6a7d.js"><link rel="prefetch" href="/assets/js/599.0bebb562.js"><link rel="prefetch" href="/assets/js/6.29d112b1.js"><link rel="prefetch" href="/assets/js/60.3bbab51d.js"><link rel="prefetch" href="/assets/js/600.1ea7596f.js"><link rel="prefetch" href="/assets/js/601.f2642bb3.js"><link rel="prefetch" href="/assets/js/602.400cc987.js"><link rel="prefetch" href="/assets/js/603.db77d173.js"><link rel="prefetch" href="/assets/js/604.0ffa30ae.js"><link rel="prefetch" href="/assets/js/605.32ca9607.js"><link rel="prefetch" href="/assets/js/606.8c1e5683.js"><link rel="prefetch" href="/assets/js/607.9c9463ef.js"><link rel="prefetch" href="/assets/js/608.d5efa77e.js"><link rel="prefetch" href="/assets/js/609.5bbffb7d.js"><link rel="prefetch" href="/assets/js/61.f7301486.js"><link rel="prefetch" href="/assets/js/610.5b0fc9da.js"><link rel="prefetch" href="/assets/js/611.bb8058c9.js"><link rel="prefetch" href="/assets/js/612.b0788f43.js"><link rel="prefetch" href="/assets/js/613.49511e65.js"><link rel="prefetch" href="/assets/js/614.fae3eacf.js"><link rel="prefetch" href="/assets/js/615.359e5899.js"><link rel="prefetch" href="/assets/js/616.905132f4.js"><link rel="prefetch" href="/assets/js/617.6c8c594e.js"><link rel="prefetch" href="/assets/js/618.6ac4f3ff.js"><link rel="prefetch" href="/assets/js/619.411a0c14.js"><link rel="prefetch" href="/assets/js/62.9aeede84.js"><link rel="prefetch" href="/assets/js/620.56155724.js"><link rel="prefetch" href="/assets/js/621.149d7933.js"><link rel="prefetch" href="/assets/js/622.f0c9bc08.js"><link rel="prefetch" href="/assets/js/623.e0989fbe.js"><link rel="prefetch" href="/assets/js/624.80b1f6a9.js"><link rel="prefetch" href="/assets/js/625.a0a392c4.js"><link rel="prefetch" href="/assets/js/626.56fd4e8a.js"><link rel="prefetch" href="/assets/js/627.264e7313.js"><link rel="prefetch" href="/assets/js/628.7a868b19.js"><link rel="prefetch" href="/assets/js/629.e7e15da1.js"><link rel="prefetch" href="/assets/js/63.4df55c8b.js"><link rel="prefetch" href="/assets/js/630.998c9b61.js"><link rel="prefetch" href="/assets/js/631.69aa049c.js"><link rel="prefetch" href="/assets/js/632.da3882c1.js"><link rel="prefetch" href="/assets/js/633.0d49adf0.js"><link rel="prefetch" href="/assets/js/634.f9984ede.js"><link rel="prefetch" href="/assets/js/635.f0439f65.js"><link rel="prefetch" href="/assets/js/636.54de4194.js"><link rel="prefetch" href="/assets/js/637.55d1c226.js"><link rel="prefetch" href="/assets/js/638.2a9a510f.js"><link rel="prefetch" href="/assets/js/639.8bec360e.js"><link rel="prefetch" href="/assets/js/64.7f3e5e81.js"><link rel="prefetch" href="/assets/js/640.30d7f96e.js"><link rel="prefetch" href="/assets/js/641.68100098.js"><link rel="prefetch" href="/assets/js/642.4b793817.js"><link rel="prefetch" href="/assets/js/643.d86a81ea.js"><link rel="prefetch" href="/assets/js/644.76327ea2.js"><link rel="prefetch" href="/assets/js/645.0ac6a923.js"><link rel="prefetch" href="/assets/js/646.cd92f728.js"><link rel="prefetch" href="/assets/js/647.f2c624e1.js"><link rel="prefetch" href="/assets/js/648.c8f3b955.js"><link rel="prefetch" href="/assets/js/649.6370753b.js"><link rel="prefetch" href="/assets/js/65.2beeae9b.js"><link rel="prefetch" href="/assets/js/650.afe31909.js"><link rel="prefetch" href="/assets/js/651.87971ec0.js"><link rel="prefetch" href="/assets/js/652.0adf10a6.js"><link rel="prefetch" href="/assets/js/653.1f655726.js"><link rel="prefetch" href="/assets/js/654.53e24c7c.js"><link rel="prefetch" href="/assets/js/655.c95a66ea.js"><link rel="prefetch" href="/assets/js/656.38b5a5ea.js"><link rel="prefetch" href="/assets/js/657.3167aa94.js"><link rel="prefetch" href="/assets/js/658.7c40ff62.js"><link rel="prefetch" href="/assets/js/659.5d2b9b54.js"><link rel="prefetch" href="/assets/js/66.44b214db.js"><link rel="prefetch" href="/assets/js/660.96a8da9e.js"><link rel="prefetch" href="/assets/js/661.4de3b6c1.js"><link rel="prefetch" href="/assets/js/662.7d9bf181.js"><link rel="prefetch" href="/assets/js/663.4ccaf40a.js"><link rel="prefetch" href="/assets/js/664.7ab4fa53.js"><link rel="prefetch" href="/assets/js/665.32245d26.js"><link rel="prefetch" href="/assets/js/666.e6617151.js"><link rel="prefetch" href="/assets/js/667.fb3b0547.js"><link rel="prefetch" href="/assets/js/668.3d1b2e36.js"><link rel="prefetch" href="/assets/js/669.b769905f.js"><link rel="prefetch" href="/assets/js/67.c31aaacf.js"><link rel="prefetch" href="/assets/js/670.88ed3af3.js"><link rel="prefetch" href="/assets/js/671.1aff6bfe.js"><link rel="prefetch" href="/assets/js/672.c90888f7.js"><link rel="prefetch" href="/assets/js/673.81241fdc.js"><link rel="prefetch" href="/assets/js/674.838a424d.js"><link rel="prefetch" href="/assets/js/675.603ac896.js"><link rel="prefetch" href="/assets/js/676.ff44b5dc.js"><link rel="prefetch" href="/assets/js/677.41a8087a.js"><link rel="prefetch" href="/assets/js/678.f0eb8d04.js"><link rel="prefetch" href="/assets/js/679.db78199e.js"><link rel="prefetch" href="/assets/js/68.08607c89.js"><link rel="prefetch" href="/assets/js/680.8fded9d4.js"><link rel="prefetch" href="/assets/js/681.0b019dfd.js"><link rel="prefetch" href="/assets/js/682.746e9190.js"><link rel="prefetch" href="/assets/js/683.d5c00845.js"><link rel="prefetch" href="/assets/js/684.b3207cad.js"><link rel="prefetch" href="/assets/js/685.d78f18ba.js"><link rel="prefetch" href="/assets/js/686.5aaecd19.js"><link rel="prefetch" href="/assets/js/687.821a06f4.js"><link rel="prefetch" href="/assets/js/688.8bbc1890.js"><link rel="prefetch" href="/assets/js/689.79b49e8c.js"><link rel="prefetch" href="/assets/js/69.509245d6.js"><link rel="prefetch" href="/assets/js/690.fa62f9dd.js"><link rel="prefetch" href="/assets/js/691.d3eb1a60.js"><link rel="prefetch" href="/assets/js/692.738f14bb.js"><link rel="prefetch" href="/assets/js/693.e6a497a2.js"><link rel="prefetch" href="/assets/js/694.6eea1c54.js"><link rel="prefetch" href="/assets/js/695.88e6acee.js"><link rel="prefetch" href="/assets/js/696.de10297f.js"><link rel="prefetch" href="/assets/js/697.96d04062.js"><link rel="prefetch" href="/assets/js/698.200cc84f.js"><link rel="prefetch" href="/assets/js/699.f11fc627.js"><link rel="prefetch" href="/assets/js/7.c16198b8.js"><link rel="prefetch" href="/assets/js/70.5f6285b1.js"><link rel="prefetch" href="/assets/js/700.93d48f59.js"><link rel="prefetch" href="/assets/js/701.b861f29a.js"><link rel="prefetch" href="/assets/js/702.dc82e05c.js"><link rel="prefetch" href="/assets/js/703.625ce87c.js"><link rel="prefetch" href="/assets/js/704.005a0a7c.js"><link rel="prefetch" href="/assets/js/705.16ad9230.js"><link rel="prefetch" href="/assets/js/706.4eead30a.js"><link rel="prefetch" href="/assets/js/707.730306ce.js"><link rel="prefetch" href="/assets/js/708.e37e743a.js"><link rel="prefetch" href="/assets/js/709.f2144f52.js"><link rel="prefetch" href="/assets/js/71.d5d0dae5.js"><link rel="prefetch" href="/assets/js/710.ee9d9b17.js"><link rel="prefetch" href="/assets/js/711.2813c338.js"><link rel="prefetch" href="/assets/js/712.e801bce4.js"><link rel="prefetch" href="/assets/js/713.21fc267c.js"><link rel="prefetch" href="/assets/js/714.4ec35525.js"><link rel="prefetch" href="/assets/js/715.fdc3cc84.js"><link rel="prefetch" href="/assets/js/716.324932ad.js"><link rel="prefetch" href="/assets/js/717.a072a66f.js"><link rel="prefetch" href="/assets/js/718.575e0305.js"><link rel="prefetch" href="/assets/js/719.5fdd55de.js"><link rel="prefetch" href="/assets/js/72.25648231.js"><link rel="prefetch" href="/assets/js/720.61477f23.js"><link rel="prefetch" href="/assets/js/721.c8bdab00.js"><link rel="prefetch" href="/assets/js/722.9255f385.js"><link rel="prefetch" href="/assets/js/723.f27792a4.js"><link rel="prefetch" href="/assets/js/724.cd504f88.js"><link rel="prefetch" href="/assets/js/725.55c845fa.js"><link rel="prefetch" href="/assets/js/726.bb49a9db.js"><link rel="prefetch" href="/assets/js/727.53d587fe.js"><link rel="prefetch" href="/assets/js/728.86972387.js"><link rel="prefetch" href="/assets/js/729.02fa0263.js"><link rel="prefetch" href="/assets/js/73.29902c1f.js"><link rel="prefetch" href="/assets/js/730.817156d1.js"><link rel="prefetch" href="/assets/js/731.6f5d6735.js"><link rel="prefetch" href="/assets/js/732.9a5ff781.js"><link rel="prefetch" href="/assets/js/733.bcb13916.js"><link rel="prefetch" href="/assets/js/734.11482b19.js"><link rel="prefetch" href="/assets/js/735.8c0d62f3.js"><link rel="prefetch" href="/assets/js/736.06465705.js"><link rel="prefetch" href="/assets/js/737.79741d87.js"><link rel="prefetch" href="/assets/js/738.cad12ff9.js"><link rel="prefetch" href="/assets/js/739.cb09e552.js"><link rel="prefetch" href="/assets/js/74.bcf666a0.js"><link rel="prefetch" href="/assets/js/740.029b1950.js"><link rel="prefetch" href="/assets/js/741.b937216a.js"><link rel="prefetch" href="/assets/js/742.ec02c706.js"><link rel="prefetch" href="/assets/js/743.70a96283.js"><link rel="prefetch" href="/assets/js/744.909b870c.js"><link rel="prefetch" href="/assets/js/745.80defb2d.js"><link rel="prefetch" href="/assets/js/746.fb972248.js"><link rel="prefetch" href="/assets/js/747.1a7b52fd.js"><link rel="prefetch" href="/assets/js/748.036f5d16.js"><link rel="prefetch" href="/assets/js/749.bd9a413d.js"><link rel="prefetch" href="/assets/js/75.23c5a54d.js"><link rel="prefetch" href="/assets/js/750.3f1ae8f5.js"><link rel="prefetch" href="/assets/js/751.8897bc9f.js"><link rel="prefetch" href="/assets/js/752.9b387659.js"><link rel="prefetch" href="/assets/js/753.f411ce21.js"><link rel="prefetch" href="/assets/js/754.26def684.js"><link rel="prefetch" href="/assets/js/755.923aff62.js"><link rel="prefetch" href="/assets/js/756.9965743a.js"><link rel="prefetch" href="/assets/js/757.0c6bbbfd.js"><link rel="prefetch" href="/assets/js/758.a830f8b1.js"><link rel="prefetch" href="/assets/js/759.987cad77.js"><link rel="prefetch" href="/assets/js/76.f54f3d4f.js"><link rel="prefetch" href="/assets/js/760.9f2652a0.js"><link rel="prefetch" href="/assets/js/761.df01a0ee.js"><link rel="prefetch" href="/assets/js/762.e0c05a1a.js"><link rel="prefetch" href="/assets/js/763.da8a60bd.js"><link rel="prefetch" href="/assets/js/764.9f2a2830.js"><link rel="prefetch" href="/assets/js/765.44e61161.js"><link rel="prefetch" href="/assets/js/766.cd7da8c1.js"><link rel="prefetch" href="/assets/js/767.6ea1fea2.js"><link rel="prefetch" href="/assets/js/768.91529b8f.js"><link rel="prefetch" href="/assets/js/769.194d7a3e.js"><link rel="prefetch" href="/assets/js/77.3d43a163.js"><link rel="prefetch" href="/assets/js/770.227fd5b9.js"><link rel="prefetch" href="/assets/js/771.44d5e37e.js"><link rel="prefetch" href="/assets/js/772.234d9bf6.js"><link rel="prefetch" href="/assets/js/773.ff1dfb6a.js"><link rel="prefetch" href="/assets/js/774.d401364f.js"><link rel="prefetch" href="/assets/js/775.37a7cf41.js"><link rel="prefetch" href="/assets/js/776.0cd10853.js"><link rel="prefetch" href="/assets/js/777.599a3a48.js"><link rel="prefetch" href="/assets/js/778.eef27a95.js"><link rel="prefetch" href="/assets/js/779.29351199.js"><link rel="prefetch" href="/assets/js/78.fd0780ac.js"><link rel="prefetch" href="/assets/js/780.74caed94.js"><link rel="prefetch" href="/assets/js/781.ee0fa9b5.js"><link rel="prefetch" href="/assets/js/782.7cffed09.js"><link rel="prefetch" href="/assets/js/783.7f01f518.js"><link rel="prefetch" href="/assets/js/784.5f65e3d7.js"><link rel="prefetch" href="/assets/js/785.d7e13880.js"><link rel="prefetch" href="/assets/js/786.6110d12f.js"><link rel="prefetch" href="/assets/js/787.334a5cdd.js"><link rel="prefetch" href="/assets/js/788.f261bc71.js"><link rel="prefetch" href="/assets/js/789.b6d74f7d.js"><link rel="prefetch" href="/assets/js/79.7b5d6224.js"><link rel="prefetch" href="/assets/js/790.fa948ec4.js"><link rel="prefetch" href="/assets/js/791.22080013.js"><link rel="prefetch" href="/assets/js/792.31ce806c.js"><link rel="prefetch" href="/assets/js/793.9fd0c56f.js"><link rel="prefetch" href="/assets/js/794.44a8cd9c.js"><link rel="prefetch" href="/assets/js/795.9f8346e5.js"><link rel="prefetch" href="/assets/js/796.0de9c7a1.js"><link rel="prefetch" href="/assets/js/797.83ac32a6.js"><link rel="prefetch" href="/assets/js/798.393fc81d.js"><link rel="prefetch" href="/assets/js/799.c1fb3981.js"><link rel="prefetch" href="/assets/js/8.3275ed06.js"><link rel="prefetch" href="/assets/js/80.df3f0a1f.js"><link rel="prefetch" href="/assets/js/800.2832adeb.js"><link rel="prefetch" href="/assets/js/801.04c58fc4.js"><link rel="prefetch" href="/assets/js/81.3d90ef6b.js"><link rel="prefetch" href="/assets/js/82.2d42448d.js"><link rel="prefetch" href="/assets/js/83.900b4de2.js"><link rel="prefetch" href="/assets/js/84.ff570f67.js"><link rel="prefetch" href="/assets/js/85.e3b3af39.js"><link rel="prefetch" href="/assets/js/86.17b5aedc.js"><link rel="prefetch" href="/assets/js/87.f931d1d6.js"><link rel="prefetch" href="/assets/js/88.d55863cd.js"><link rel="prefetch" href="/assets/js/89.15a9a6d7.js"><link rel="prefetch" href="/assets/js/9.04948a9d.js"><link rel="prefetch" href="/assets/js/90.22696aa9.js"><link rel="prefetch" href="/assets/js/91.f1bd8a2e.js"><link rel="prefetch" href="/assets/js/92.85733094.js"><link rel="prefetch" href="/assets/js/93.59bacfd7.js"><link rel="prefetch" href="/assets/js/94.a5f9b7a0.js"><link rel="prefetch" href="/assets/js/95.be52d65a.js"><link rel="prefetch" href="/assets/js/96.0b76ba8e.js"><link rel="prefetch" href="/assets/js/97.28183cd4.js"><link rel="prefetch" href="/assets/js/98.2d22829c.js"><link rel="prefetch" href="/assets/js/99.ed602a20.js">
    <link rel="stylesheet" href="/assets/css/0.styles.a3df589e.css">
  </head>
  <body>
    <div id="app" data-server-rendered="true"><div class="theme-container no-sidebar"><header class="navbar"><div class="sidebar-button"><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" role="img" viewBox="0 0 448 512" class="icon"><path fill="currentColor" d="M436 124H12c-6.627 0-12-5.373-12-12V80c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12z"></path></svg></div> <a href="/" class="home-link router-link-active"><!----> <span class="site-name">AJ</span></a> <div class="links"><div class="search-box"><input aria-label="Search" autocomplete="off" spellcheck="false" value=""> <!----></div> <nav class="nav-links can-hide"><div class="nav-item"><a href="/" class="nav-link">主页</a></div><div class="nav-item"><a href="/op/" class="nav-link">Devops</a></div><div class="nav-item"><a href="/golang/" class="nav-link">Go</a></div><div class="nav-item"><a href="/go-block/" class="nav-link">区块链</a></div><div class="nav-item"><a href="/k8s/" class="nav-link">k8s</a></div><div class="nav-item"><a href="/about.html" class="nav-link">关于我</a></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="更多" class="dropdown-title"><span class="title">更多</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/go-learning/" class="nav-link">go-learning</a></li><li class="dropdown-item"><!----> <a href="/post/flutter-guide/" class="nav-link">flutter</a></li><li class="dropdown-item"><!----> <a href="/mysql/" class="nav-link">mysql</a></li><li class="dropdown-item"><!----> <a href="/python/" class="nav-link">python</a></li></ul></div></div> <a href="https://github.com/ChinaArJun" target="_blank" rel="noopener noreferrer" class="repo-link">
    GitHub
    <svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></nav></div></header> <div class="sidebar-mask"></div> <aside class="sidebar"><nav class="nav-links"><div class="nav-item"><a href="/" class="nav-link">主页</a></div><div class="nav-item"><a href="/op/" class="nav-link">Devops</a></div><div class="nav-item"><a href="/golang/" class="nav-link">Go</a></div><div class="nav-item"><a href="/go-block/" class="nav-link">区块链</a></div><div class="nav-item"><a href="/k8s/" class="nav-link">k8s</a></div><div class="nav-item"><a href="/about.html" class="nav-link">关于我</a></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="更多" class="dropdown-title"><span class="title">更多</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/go-learning/" class="nav-link">go-learning</a></li><li class="dropdown-item"><!----> <a href="/post/flutter-guide/" class="nav-link">flutter</a></li><li class="dropdown-item"><!----> <a href="/mysql/" class="nav-link">mysql</a></li><li class="dropdown-item"><!----> <a href="/python/" class="nav-link">python</a></li></ul></div></div> <a href="https://github.com/ChinaArJun" target="_blank" rel="noopener noreferrer" class="repo-link">
    GitHub
    <svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></nav> <div></div> <div style="padding-left:1.5rem;"><div></div></div> <!----> </aside> <!----> <!----> <main class="page"><div class="theme-default-content" style="margin-bottom:-5rem;"><div class="bar"><div class="bar-intro"><div class="text">
      流逝的是岁月，不变的是情怀.
        </div> <div class="text">
      坚持学习，是为了成就更好的自己. <br></div> <div>公众号[中关村程序员]</div></div></div> <!----></div> <div class="theme-default-content content__default"><h1 id="动态规划"><a href="#动态规划" class="header-anchor">#</a> 动态规划</h1> <h2 id="背景"><a href="#背景" class="header-anchor">#</a> 背景</h2> <p>先从一道题目开始~</p> <p>如题  <a href="https://leetcode-cn.com/problems/triangle/" target="_blank" rel="noopener noreferrer">triangle<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></p> <blockquote><p>给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。</p></blockquote> <p>例如，给定三角形：</p> <div class="language-text extra-class"><pre class="language-text"><code>[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]
</code></pre></div><p>自顶向下的最小路径和为  11（即，2 + 3 + 5 + 1 = 11）。</p> <p>使用 DFS（遍历 或者 分治法）</p> <p>遍历</p> <p><img src="https://img.fuiboom.com/img/dp_triangle.png" alt="image.png"></p> <p>分治法</p> <p><img src="https://img.fuiboom.com/img/dp_dc.png" alt="image.png"></p> <p>优化 DFS，缓存已经被计算的值（称为：记忆化搜索 本质上：动态规划）</p> <p><img src="https://img.fuiboom.com/img/dp_memory_search.png" alt="image.png"></p> <p>动态规划就是把大问题变成小问题，并解决了小问题重复计算的方法称为动态规划</p> <p>动态规划和 DFS 区别</p> <ul><li>二叉树 子问题是没有交集，所以大部分二叉树都用递归或者分治法，即 DFS，就可以解决</li> <li>像 triangle 这种是有重复走的情况，<strong>子问题是有交集</strong>，所以可以用动态规划来解决</li></ul> <p>动态规划，自底向上</p> <div class="language-go extra-class"><pre class="language-go"><code><span class="token keyword">func</span> <span class="token function">minimumTotal</span><span class="token punctuation">(</span>triangle <span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token builtin">int</span><span class="token punctuation">)</span> <span class="token builtin">int</span> <span class="token punctuation">{</span>
	<span class="token keyword">if</span> <span class="token function">len</span><span class="token punctuation">(</span>triangle<span class="token punctuation">)</span> <span class="token operator">==</span> <span class="token number">0</span> <span class="token operator">||</span> <span class="token function">len</span><span class="token punctuation">(</span>triangle<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token operator">==</span> <span class="token number">0</span> <span class="token punctuation">{</span>
		<span class="token keyword">return</span> <span class="token number">0</span>
	<span class="token punctuation">}</span>
	<span class="token comment">// 1、状态定义：f[i][j] 表示从i,j出发，到达最后一层的最短路径</span>
	<span class="token keyword">var</span> l <span class="token operator">=</span> <span class="token function">len</span><span class="token punctuation">(</span>triangle<span class="token punctuation">)</span>
	<span class="token keyword">var</span> f <span class="token operator">=</span> <span class="token function">make</span><span class="token punctuation">(</span><span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token builtin">int</span><span class="token punctuation">,</span> l<span class="token punctuation">)</span>
	<span class="token comment">// 2、初始化</span>
	<span class="token keyword">for</span> i <span class="token operator">:=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> l<span class="token punctuation">;</span> i<span class="token operator">++</span> <span class="token punctuation">{</span>
		<span class="token keyword">for</span> j <span class="token operator">:=</span> <span class="token number">0</span><span class="token punctuation">;</span> j <span class="token operator">&lt;</span> <span class="token function">len</span><span class="token punctuation">(</span>triangle<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span> j<span class="token operator">++</span> <span class="token punctuation">{</span>
			<span class="token keyword">if</span> f<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">==</span> <span class="token boolean">nil</span> <span class="token punctuation">{</span>
				f<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token function">make</span><span class="token punctuation">(</span><span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token builtin">int</span><span class="token punctuation">,</span> <span class="token function">len</span><span class="token punctuation">(</span>triangle<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">)</span>
			<span class="token punctuation">}</span>
			f<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">=</span> triangle<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span>
		<span class="token punctuation">}</span>
	<span class="token punctuation">}</span>
	<span class="token comment">// 3、递推求解</span>
	<span class="token keyword">for</span> i <span class="token operator">:=</span> <span class="token function">len</span><span class="token punctuation">(</span>triangle<span class="token punctuation">)</span> <span class="token operator">-</span> <span class="token number">2</span><span class="token punctuation">;</span> i <span class="token operator">&gt;=</span> <span class="token number">0</span><span class="token punctuation">;</span> i<span class="token operator">--</span> <span class="token punctuation">{</span>
		<span class="token keyword">for</span> j <span class="token operator">:=</span> <span class="token number">0</span><span class="token punctuation">;</span> j <span class="token operator">&lt;</span> <span class="token function">len</span><span class="token punctuation">(</span>triangle<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span> j<span class="token operator">++</span> <span class="token punctuation">{</span>
			f<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token function">min</span><span class="token punctuation">(</span>f<span class="token punctuation">[</span>i<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">,</span> f<span class="token punctuation">[</span>i<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token operator">+</span> triangle<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span>
		<span class="token punctuation">}</span>
	<span class="token punctuation">}</span>
	<span class="token comment">// 4、答案</span>
	<span class="token keyword">return</span> f<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span>
<span class="token punctuation">}</span>
<span class="token keyword">func</span> <span class="token function">min</span><span class="token punctuation">(</span>a<span class="token punctuation">,</span> b <span class="token builtin">int</span><span class="token punctuation">)</span> <span class="token builtin">int</span> <span class="token punctuation">{</span>
	<span class="token keyword">if</span> a <span class="token operator">&gt;</span> b <span class="token punctuation">{</span>
		<span class="token keyword">return</span> b
	<span class="token punctuation">}</span>
	<span class="token keyword">return</span> a
<span class="token punctuation">}</span>

</code></pre></div><p>动态规划，自顶向下</p> <div class="language-go extra-class"><pre class="language-go"><code><span class="token comment">// 测试用例：</span>
<span class="token comment">// [</span>
<span class="token comment">// [2],</span>
<span class="token comment">// [3,4],</span>
<span class="token comment">// [6,5,7],</span>
<span class="token comment">// [4,1,8,3]</span>
<span class="token comment">// ]</span>
<span class="token keyword">func</span> <span class="token function">minimumTotal</span><span class="token punctuation">(</span>triangle <span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token builtin">int</span><span class="token punctuation">)</span> <span class="token builtin">int</span> <span class="token punctuation">{</span>
    <span class="token keyword">if</span> <span class="token function">len</span><span class="token punctuation">(</span>triangle<span class="token punctuation">)</span> <span class="token operator">==</span> <span class="token number">0</span> <span class="token operator">||</span> <span class="token function">len</span><span class="token punctuation">(</span>triangle<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token operator">==</span> <span class="token number">0</span> <span class="token punctuation">{</span>
        <span class="token keyword">return</span> <span class="token number">0</span>
    <span class="token punctuation">}</span>
    <span class="token comment">// 1、状态定义：f[i][j] 表示从0,0出发，到达i,j的最短路径</span>
    <span class="token keyword">var</span> l <span class="token operator">=</span> <span class="token function">len</span><span class="token punctuation">(</span>triangle<span class="token punctuation">)</span>
    <span class="token keyword">var</span> f <span class="token operator">=</span> <span class="token function">make</span><span class="token punctuation">(</span><span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token builtin">int</span><span class="token punctuation">,</span> l<span class="token punctuation">)</span>
    <span class="token comment">// 2、初始化</span>
    <span class="token keyword">for</span> i <span class="token operator">:=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> l<span class="token punctuation">;</span> i<span class="token operator">++</span> <span class="token punctuation">{</span>
        <span class="token keyword">for</span> j <span class="token operator">:=</span> <span class="token number">0</span><span class="token punctuation">;</span> j <span class="token operator">&lt;</span> <span class="token function">len</span><span class="token punctuation">(</span>triangle<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span> j<span class="token operator">++</span> <span class="token punctuation">{</span>
            <span class="token keyword">if</span> f<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">==</span> <span class="token boolean">nil</span> <span class="token punctuation">{</span>
                f<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token function">make</span><span class="token punctuation">(</span><span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token builtin">int</span><span class="token punctuation">,</span> <span class="token function">len</span><span class="token punctuation">(</span>triangle<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">)</span>
            <span class="token punctuation">}</span>
            f<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">=</span> triangle<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span>
        <span class="token punctuation">}</span>
    <span class="token punctuation">}</span>
    <span class="token comment">// 递推求解</span>
    <span class="token keyword">for</span> i <span class="token operator">:=</span> <span class="token number">1</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> l<span class="token punctuation">;</span> i<span class="token operator">++</span> <span class="token punctuation">{</span>
        <span class="token keyword">for</span> j <span class="token operator">:=</span> <span class="token number">0</span><span class="token punctuation">;</span> j <span class="token operator">&lt;</span> <span class="token function">len</span><span class="token punctuation">(</span>triangle<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span> j<span class="token operator">++</span> <span class="token punctuation">{</span>
            <span class="token comment">// 这里分为两种情况：</span>
            <span class="token comment">// 1、上一层没有左边值</span>
            <span class="token comment">// 2、上一层没有右边值</span>
            <span class="token keyword">if</span> j<span class="token operator">-</span><span class="token number">1</span> <span class="token operator">&lt;</span> <span class="token number">0</span> <span class="token punctuation">{</span>
                f<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">=</span> f<span class="token punctuation">[</span>i<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">+</span> triangle<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span>
            <span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token keyword">if</span> j <span class="token operator">&gt;=</span> <span class="token function">len</span><span class="token punctuation">(</span>f<span class="token punctuation">[</span>i<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
                f<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">=</span> f<span class="token punctuation">[</span>i<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span> <span class="token operator">+</span> triangle<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span>
            <span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token punctuation">{</span>
                f<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token function">min</span><span class="token punctuation">(</span>f<span class="token punctuation">[</span>i<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">,</span> f<span class="token punctuation">[</span>i<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token operator">+</span> triangle<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span>
            <span class="token punctuation">}</span>
        <span class="token punctuation">}</span>
    <span class="token punctuation">}</span>
    result <span class="token operator">:=</span> f<span class="token punctuation">[</span>l<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span>
    <span class="token keyword">for</span> i <span class="token operator">:=</span> <span class="token number">1</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> <span class="token function">len</span><span class="token punctuation">(</span>f<span class="token punctuation">[</span>l<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span> i<span class="token operator">++</span> <span class="token punctuation">{</span>
        result <span class="token operator">=</span> <span class="token function">min</span><span class="token punctuation">(</span>result<span class="token punctuation">,</span> f<span class="token punctuation">[</span>l<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span>
    <span class="token punctuation">}</span>
    <span class="token keyword">return</span> result
<span class="token punctuation">}</span>
<span class="token keyword">func</span> <span class="token function">min</span><span class="token punctuation">(</span>a<span class="token punctuation">,</span> b <span class="token builtin">int</span><span class="token punctuation">)</span> <span class="token builtin">int</span> <span class="token punctuation">{</span>
    <span class="token keyword">if</span> a <span class="token operator">&gt;</span> b <span class="token punctuation">{</span>
        <span class="token keyword">return</span> b
    <span class="token punctuation">}</span>
    <span class="token keyword">return</span> a
<span class="token punctuation">}</span>
</code></pre></div><h2 id="递归和动规关系"><a href="#递归和动规关系" class="header-anchor">#</a> 递归和动规关系</h2> <p>递归是一种程序的实现方式：函数的自我调用</p> <div class="language-go extra-class"><pre class="language-go"><code><span class="token function">Function</span><span class="token punctuation">(</span>x<span class="token punctuation">)</span> <span class="token punctuation">{</span>
	<span class="token operator">...</span>
	<span class="token function">Funciton</span><span class="token punctuation">(</span>x<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token operator">...</span>
<span class="token punctuation">}</span>
</code></pre></div><p>动态规划：是一种解决问 题的思想，大规模问题的结果，是由小规模问 题的结果运算得来的。动态规划可用递归来实现(Memorization Search)</p> <h2 id="使用场景"><a href="#使用场景" class="header-anchor">#</a> 使用场景</h2> <p>满足两个条件</p> <ul><li>满足以下条件之一
<ul><li>求最大/最小值（Maximum/Minimum ）</li> <li>求是否可行（Yes/No ）</li> <li>求可行个数（Count(*) ）</li></ul></li> <li>满足不能排序或者交换（Can not sort / swap ）</li></ul> <p>如题：<a href="https://leetcode-cn.com/problems/longest-consecutive-sequence/" target="_blank" rel="noopener noreferrer">longest-consecutive-sequence<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a>  位置可以交换，所以不用动态规划</p> <h2 id="四点要素"><a href="#四点要素" class="header-anchor">#</a> 四点要素</h2> <ol><li><strong>状态 State</strong> <ul><li>灵感，创造力，存储小规模问题的结果</li></ul></li> <li>方程 Function
<ul><li>状态之间的联系，怎么通过小的状态，来算大的状态</li></ul></li> <li>初始化 Intialization
<ul><li>最极限的小状态是什么, 起点</li></ul></li> <li>答案 Answer
<ul><li>最大的那个状态是什么，终点</li></ul></li></ol> <h2 id="常见四种类型"><a href="#常见四种类型" class="header-anchor">#</a> 常见四种类型</h2> <ol><li>Matrix DP (10%)</li> <li>Sequence (40%)</li> <li>Two Sequences DP (40%)</li> <li>Backpack (10%)</li></ol> <blockquote><p>注意点</p> <ul><li>贪心算法大多题目靠背答案，所以如果能用动态规划就尽量用动规，不用贪心算法</li></ul></blockquote> <h2 id="_1、矩阵类型（10-）"><a href="#_1、矩阵类型（10-）" class="header-anchor">#</a> 1、矩阵类型（10%）</h2> <h3 id="minimum-path-sum"><a href="#minimum-path-sum" class="header-anchor">#</a> <a href="https://leetcode-cn.com/problems/minimum-path-sum/" target="_blank" rel="noopener noreferrer">minimum-path-sum<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></h3> <blockquote><p>给定一个包含非负整数的  <em>m</em> x <em>n</em>  网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。</p></blockquote> <p>思路：动态规划
1、state: f[x][y]从起点走到 x,y 的最短路径
2、function: f[x][y] = min(f[x-1][y], f[x][y-1]) + A[x][y]
3、intialize: f[0][0] = A[0][0]、f[i][0] = sum(0,0 -&gt; i,0)、 f[0][i] = sum(0,0 -&gt; 0,i)
4、answer: f[n-1][m-1]</p> <div class="language-go extra-class"><pre class="language-go"><code><span class="token keyword">func</span> <span class="token function">minPathSum</span><span class="token punctuation">(</span>grid <span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token builtin">int</span><span class="token punctuation">)</span> <span class="token builtin">int</span> <span class="token punctuation">{</span>
    <span class="token comment">// 思路：动态规划</span>
    <span class="token comment">// f[i][j] 表示i,j到0,0的和最小</span>
    <span class="token keyword">if</span> <span class="token function">len</span><span class="token punctuation">(</span>grid<span class="token punctuation">)</span> <span class="token operator">==</span> <span class="token number">0</span> <span class="token operator">||</span> <span class="token function">len</span><span class="token punctuation">(</span>grid<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token operator">==</span> <span class="token number">0</span> <span class="token punctuation">{</span>
        <span class="token keyword">return</span> <span class="token number">0</span>
    <span class="token punctuation">}</span>
    <span class="token comment">// 复用原来的矩阵列表</span>
    <span class="token comment">// 初始化：f[i][0]、f[0][j]</span>
    <span class="token keyword">for</span> i <span class="token operator">:=</span> <span class="token number">1</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> <span class="token function">len</span><span class="token punctuation">(</span>grid<span class="token punctuation">)</span><span class="token punctuation">;</span> i<span class="token operator">++</span> <span class="token punctuation">{</span>
        grid<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span> <span class="token operator">=</span> grid<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span> <span class="token operator">+</span> grid<span class="token punctuation">[</span>i<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span>
    <span class="token punctuation">}</span>
    <span class="token keyword">for</span> j <span class="token operator">:=</span> <span class="token number">1</span><span class="token punctuation">;</span> j <span class="token operator">&lt;</span> <span class="token function">len</span><span class="token punctuation">(</span>grid<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span> j<span class="token operator">++</span> <span class="token punctuation">{</span>
        grid<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">=</span> grid<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">+</span> grid<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span>
    <span class="token punctuation">}</span>
    <span class="token keyword">for</span> i <span class="token operator">:=</span> <span class="token number">1</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> <span class="token function">len</span><span class="token punctuation">(</span>grid<span class="token punctuation">)</span><span class="token punctuation">;</span> i<span class="token operator">++</span> <span class="token punctuation">{</span>
        <span class="token keyword">for</span> j <span class="token operator">:=</span> <span class="token number">1</span><span class="token punctuation">;</span> j <span class="token operator">&lt;</span> <span class="token function">len</span><span class="token punctuation">(</span>grid<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span> j<span class="token operator">++</span> <span class="token punctuation">{</span>
            grid<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token function">min</span><span class="token punctuation">(</span>grid<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">,</span> grid<span class="token punctuation">[</span>i<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token operator">+</span> grid<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span>
        <span class="token punctuation">}</span>
    <span class="token punctuation">}</span>
    <span class="token keyword">return</span> grid<span class="token punctuation">[</span><span class="token function">len</span><span class="token punctuation">(</span>grid<span class="token punctuation">)</span><span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token function">len</span><span class="token punctuation">(</span>grid<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span>
<span class="token punctuation">}</span>
<span class="token keyword">func</span> <span class="token function">min</span><span class="token punctuation">(</span>a<span class="token punctuation">,</span> b <span class="token builtin">int</span><span class="token punctuation">)</span> <span class="token builtin">int</span> <span class="token punctuation">{</span>
    <span class="token keyword">if</span> a <span class="token operator">&gt;</span> b <span class="token punctuation">{</span>
        <span class="token keyword">return</span> b
    <span class="token punctuation">}</span>
    <span class="token keyword">return</span> a
<span class="token punctuation">}</span>
</code></pre></div><h3 id="unique-paths"><a href="#unique-paths" class="header-anchor">#</a> <a href="https://leetcode-cn.com/problems/unique-paths/" target="_blank" rel="noopener noreferrer">unique-paths<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></h3> <blockquote><p>一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
问总共有多少条不同的路径？</p></blockquote> <div class="language-go extra-class"><pre class="language-go"><code><span class="token keyword">func</span> <span class="token function">uniquePaths</span><span class="token punctuation">(</span>m <span class="token builtin">int</span><span class="token punctuation">,</span> n <span class="token builtin">int</span><span class="token punctuation">)</span> <span class="token builtin">int</span> <span class="token punctuation">{</span>
	<span class="token comment">// f[i][j] 表示i,j到0,0路径数</span>
	f <span class="token operator">:=</span> <span class="token function">make</span><span class="token punctuation">(</span><span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token builtin">int</span><span class="token punctuation">,</span> m<span class="token punctuation">)</span>
	<span class="token keyword">for</span> i <span class="token operator">:=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> m<span class="token punctuation">;</span> i<span class="token operator">++</span> <span class="token punctuation">{</span>
		<span class="token keyword">for</span> j <span class="token operator">:=</span> <span class="token number">0</span><span class="token punctuation">;</span> j <span class="token operator">&lt;</span> n<span class="token punctuation">;</span> j<span class="token operator">++</span> <span class="token punctuation">{</span>
			<span class="token keyword">if</span> f<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">==</span> <span class="token boolean">nil</span> <span class="token punctuation">{</span>
				f<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token function">make</span><span class="token punctuation">(</span><span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token builtin">int</span><span class="token punctuation">,</span> n<span class="token punctuation">)</span>
			<span class="token punctuation">}</span>
			f<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token number">1</span>
		<span class="token punctuation">}</span>
	<span class="token punctuation">}</span>
	<span class="token keyword">for</span> i <span class="token operator">:=</span> <span class="token number">1</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> m<span class="token punctuation">;</span> i<span class="token operator">++</span> <span class="token punctuation">{</span>
		<span class="token keyword">for</span> j <span class="token operator">:=</span> <span class="token number">1</span><span class="token punctuation">;</span> j <span class="token operator">&lt;</span> n<span class="token punctuation">;</span> j<span class="token operator">++</span> <span class="token punctuation">{</span>
			f<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">=</span> f<span class="token punctuation">[</span>i<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">+</span> f<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span>
		<span class="token punctuation">}</span>
	<span class="token punctuation">}</span>
	<span class="token keyword">return</span> f<span class="token punctuation">[</span>m<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">[</span>n<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span>
<span class="token punctuation">}</span>
</code></pre></div><h3 id="unique-paths-ii"><a href="#unique-paths-ii" class="header-anchor">#</a> <a href="https://leetcode-cn.com/problems/unique-paths-ii/" target="_blank" rel="noopener noreferrer">unique-paths-ii<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></h3> <blockquote><p>一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
问总共有多少条不同的路径？
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？</p></blockquote> <div class="language-go extra-class"><pre class="language-go"><code><span class="token keyword">func</span> <span class="token function">uniquePathsWithObstacles</span><span class="token punctuation">(</span>obstacleGrid <span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token builtin">int</span><span class="token punctuation">)</span> <span class="token builtin">int</span> <span class="token punctuation">{</span>
	<span class="token comment">// f[i][j] = f[i-1][j] + f[i][j-1] 并检查障碍物</span>
	<span class="token keyword">if</span> obstacleGrid<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span> <span class="token operator">==</span> <span class="token number">1</span> <span class="token punctuation">{</span>
		<span class="token keyword">return</span> <span class="token number">0</span>
	<span class="token punctuation">}</span>
	m <span class="token operator">:=</span> <span class="token function">len</span><span class="token punctuation">(</span>obstacleGrid<span class="token punctuation">)</span>
	n <span class="token operator">:=</span> <span class="token function">len</span><span class="token punctuation">(</span>obstacleGrid<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">)</span>
	f <span class="token operator">:=</span> <span class="token function">make</span><span class="token punctuation">(</span><span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token builtin">int</span><span class="token punctuation">,</span> m<span class="token punctuation">)</span>
	<span class="token keyword">for</span> i <span class="token operator">:=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> m<span class="token punctuation">;</span> i<span class="token operator">++</span> <span class="token punctuation">{</span>
		<span class="token keyword">for</span> j <span class="token operator">:=</span> <span class="token number">0</span><span class="token punctuation">;</span> j <span class="token operator">&lt;</span> n<span class="token punctuation">;</span> j<span class="token operator">++</span> <span class="token punctuation">{</span>
			<span class="token keyword">if</span> f<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">==</span> <span class="token boolean">nil</span> <span class="token punctuation">{</span>
				f<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token function">make</span><span class="token punctuation">(</span><span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token builtin">int</span><span class="token punctuation">,</span> n<span class="token punctuation">)</span>
			<span class="token punctuation">}</span>
			f<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token number">1</span>
		<span class="token punctuation">}</span>
	<span class="token punctuation">}</span>
	<span class="token keyword">for</span> i <span class="token operator">:=</span> <span class="token number">1</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> m<span class="token punctuation">;</span> i<span class="token operator">++</span> <span class="token punctuation">{</span>
		<span class="token keyword">if</span> obstacleGrid<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span> <span class="token operator">==</span> <span class="token number">1</span> <span class="token operator">||</span> f<span class="token punctuation">[</span>i<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span> <span class="token operator">==</span> <span class="token number">0</span> <span class="token punctuation">{</span>
			f<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token number">0</span>
		<span class="token punctuation">}</span>
	<span class="token punctuation">}</span>
	<span class="token keyword">for</span> j <span class="token operator">:=</span> <span class="token number">1</span><span class="token punctuation">;</span> j <span class="token operator">&lt;</span> n<span class="token punctuation">;</span> j<span class="token operator">++</span> <span class="token punctuation">{</span>
		<span class="token keyword">if</span> obstacleGrid<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">==</span> <span class="token number">1</span> <span class="token operator">||</span> f<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span> <span class="token operator">==</span> <span class="token number">0</span> <span class="token punctuation">{</span>
			f<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token number">0</span>
		<span class="token punctuation">}</span>
	<span class="token punctuation">}</span>
	<span class="token keyword">for</span> i <span class="token operator">:=</span> <span class="token number">1</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> m<span class="token punctuation">;</span> i<span class="token operator">++</span> <span class="token punctuation">{</span>
		<span class="token keyword">for</span> j <span class="token operator">:=</span> <span class="token number">1</span><span class="token punctuation">;</span> j <span class="token operator">&lt;</span> n<span class="token punctuation">;</span> j<span class="token operator">++</span> <span class="token punctuation">{</span>
			<span class="token keyword">if</span> obstacleGrid<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">==</span> <span class="token number">1</span> <span class="token punctuation">{</span>
				f<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token number">0</span>
			<span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token punctuation">{</span>
				f<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">=</span> f<span class="token punctuation">[</span>i<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">+</span> f<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span>
			<span class="token punctuation">}</span>
		<span class="token punctuation">}</span>
	<span class="token punctuation">}</span>
	<span class="token keyword">return</span> f<span class="token punctuation">[</span>m<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">[</span>n<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span>
<span class="token punctuation">}</span>
</code></pre></div><h2 id="_2、序列类型（40-）"><a href="#_2、序列类型（40-）" class="header-anchor">#</a> 2、序列类型（40%）</h2> <h3 id="climbing-stairs"><a href="#climbing-stairs" class="header-anchor">#</a> <a href="https://leetcode-cn.com/problems/climbing-stairs/" target="_blank" rel="noopener noreferrer">climbing-stairs<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></h3> <blockquote><p>假设你正在爬楼梯。需要  <em>n</em>  阶你才能到达楼顶。</p></blockquote> <div class="language-go extra-class"><pre class="language-go"><code><span class="token keyword">func</span> <span class="token function">climbStairs</span><span class="token punctuation">(</span>n <span class="token builtin">int</span><span class="token punctuation">)</span> <span class="token builtin">int</span> <span class="token punctuation">{</span>
    <span class="token comment">// f[i] = f[i-1] + f[i-2]</span>
    <span class="token keyword">if</span> n <span class="token operator">==</span> <span class="token number">1</span> <span class="token operator">||</span> n <span class="token operator">==</span> <span class="token number">0</span> <span class="token punctuation">{</span>
        <span class="token keyword">return</span> n
    <span class="token punctuation">}</span>
    f <span class="token operator">:=</span> <span class="token function">make</span><span class="token punctuation">(</span><span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token builtin">int</span><span class="token punctuation">,</span> n<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">)</span>
    f<span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token number">1</span>
    f<span class="token punctuation">[</span><span class="token number">2</span><span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token number">2</span>
    <span class="token keyword">for</span> i <span class="token operator">:=</span> <span class="token number">3</span><span class="token punctuation">;</span> i <span class="token operator">&lt;=</span> n<span class="token punctuation">;</span> i<span class="token operator">++</span> <span class="token punctuation">{</span>
        f<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> f<span class="token punctuation">[</span>i<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span> <span class="token operator">+</span> f<span class="token punctuation">[</span>i<span class="token operator">-</span><span class="token number">2</span><span class="token punctuation">]</span>
    <span class="token punctuation">}</span>
    <span class="token keyword">return</span> f<span class="token punctuation">[</span>n<span class="token punctuation">]</span>
<span class="token punctuation">}</span>
</code></pre></div><h3 id="jump-game"><a href="#jump-game" class="header-anchor">#</a> <a href="https://leetcode-cn.com/problems/jump-game/" target="_blank" rel="noopener noreferrer">jump-game<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></h3> <blockquote><p>给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个位置。</p></blockquote> <div class="language-go extra-class"><pre class="language-go"><code><span class="token keyword">func</span> <span class="token function">canJump</span><span class="token punctuation">(</span>nums <span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token builtin">int</span><span class="token punctuation">)</span> <span class="token builtin">bool</span> <span class="token punctuation">{</span>
    <span class="token comment">// 思路：看最后一跳</span>
    <span class="token comment">// 状态：f[i] 表示是否能从0跳到i</span>
    <span class="token comment">// 推导：f[i] = OR(f[j],j&lt;i&amp;&amp;j能跳到i) 判断之前所有的点最后一跳是否能跳到当前点</span>
    <span class="token comment">// 初始化：f[0] = 0</span>
    <span class="token comment">// 结果： f[n-1]</span>
    <span class="token keyword">if</span> <span class="token function">len</span><span class="token punctuation">(</span>nums<span class="token punctuation">)</span> <span class="token operator">==</span> <span class="token number">0</span> <span class="token punctuation">{</span>
        <span class="token keyword">return</span> <span class="token boolean">true</span>
    <span class="token punctuation">}</span>
    f <span class="token operator">:=</span> <span class="token function">make</span><span class="token punctuation">(</span><span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token builtin">bool</span><span class="token punctuation">,</span> <span class="token function">len</span><span class="token punctuation">(</span>nums<span class="token punctuation">)</span><span class="token punctuation">)</span>
    f<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token boolean">true</span>
    <span class="token keyword">for</span> i <span class="token operator">:=</span> <span class="token number">1</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> <span class="token function">len</span><span class="token punctuation">(</span>nums<span class="token punctuation">)</span><span class="token punctuation">;</span> i<span class="token operator">++</span> <span class="token punctuation">{</span>
        <span class="token keyword">for</span> j <span class="token operator">:=</span> <span class="token number">0</span><span class="token punctuation">;</span> j <span class="token operator">&lt;</span> i<span class="token punctuation">;</span> j<span class="token operator">++</span> <span class="token punctuation">{</span>
            <span class="token keyword">if</span> f<span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">==</span> <span class="token boolean">true</span> <span class="token operator">&amp;&amp;</span> nums<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token operator">+</span>j <span class="token operator">&gt;=</span> i <span class="token punctuation">{</span>
                f<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token boolean">true</span>
            <span class="token punctuation">}</span>
        <span class="token punctuation">}</span>
    <span class="token punctuation">}</span>
    <span class="token keyword">return</span> f<span class="token punctuation">[</span><span class="token function">len</span><span class="token punctuation">(</span>nums<span class="token punctuation">)</span><span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span>
<span class="token punctuation">}</span>
</code></pre></div><h3 id="jump-game-ii"><a href="#jump-game-ii" class="header-anchor">#</a> <a href="https://leetcode-cn.com/problems/jump-game-ii/" target="_blank" rel="noopener noreferrer">jump-game-ii<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></h3> <blockquote><p>给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。</p></blockquote> <div class="language-go extra-class"><pre class="language-go"><code><span class="token keyword">func</span> <span class="token function">jump</span><span class="token punctuation">(</span>nums <span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token builtin">int</span><span class="token punctuation">)</span> <span class="token builtin">int</span> <span class="token punctuation">{</span>
    <span class="token comment">// 状态：f[i] 表示从起点到当前位置最小次数</span>
    <span class="token comment">// 推导：f[i] = f[j],a[j]+j &gt;=i,min(f[j]+1)</span>
    <span class="token comment">// 初始化：f[0] = 0</span>
    <span class="token comment">// 结果：f[n-1]</span>
    f <span class="token operator">:=</span> <span class="token function">make</span><span class="token punctuation">(</span><span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token builtin">int</span><span class="token punctuation">,</span> <span class="token function">len</span><span class="token punctuation">(</span>nums<span class="token punctuation">)</span><span class="token punctuation">)</span>
    f<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token number">0</span>
    <span class="token keyword">for</span> i <span class="token operator">:=</span> <span class="token number">1</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> <span class="token function">len</span><span class="token punctuation">(</span>nums<span class="token punctuation">)</span><span class="token punctuation">;</span> i<span class="token operator">++</span> <span class="token punctuation">{</span>
        <span class="token comment">// f[i] 最大值为i</span>
        f<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> i
        <span class="token comment">// 遍历之前结果取一个最小值+1</span>
        <span class="token keyword">for</span> j <span class="token operator">:=</span> <span class="token number">0</span><span class="token punctuation">;</span> j <span class="token operator">&lt;</span> i<span class="token punctuation">;</span> j<span class="token operator">++</span> <span class="token punctuation">{</span>
            <span class="token keyword">if</span> nums<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token operator">+</span>j <span class="token operator">&gt;=</span> i <span class="token punctuation">{</span>
                f<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token function">min</span><span class="token punctuation">(</span>f<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">,</span>f<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span>
            <span class="token punctuation">}</span>
        <span class="token punctuation">}</span>
    <span class="token punctuation">}</span>
    <span class="token keyword">return</span> f<span class="token punctuation">[</span><span class="token function">len</span><span class="token punctuation">(</span>nums<span class="token punctuation">)</span><span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span>
<span class="token punctuation">}</span>
<span class="token keyword">func</span> <span class="token function">min</span><span class="token punctuation">(</span>a<span class="token punctuation">,</span> b <span class="token builtin">int</span><span class="token punctuation">)</span> <span class="token builtin">int</span> <span class="token punctuation">{</span>
    <span class="token keyword">if</span> a <span class="token operator">&gt;</span> b <span class="token punctuation">{</span>
        <span class="token keyword">return</span> b
    <span class="token punctuation">}</span>
    <span class="token keyword">return</span> a
<span class="token punctuation">}</span>
</code></pre></div><h3 id="palindrome-partitioning-ii"><a href="#palindrome-partitioning-ii" class="header-anchor">#</a> <a href="https://leetcode-cn.com/problems/palindrome-partitioning-ii/" target="_blank" rel="noopener noreferrer">palindrome-partitioning-ii<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></h3> <blockquote><p>给定一个字符串 <em>s</em>，将 <em>s</em> 分割成一些子串，使每个子串都是回文串。
返回符合要求的最少分割次数。</p></blockquote> <div class="language-go extra-class"><pre class="language-go"><code><span class="token keyword">func</span> <span class="token function">minCut</span><span class="token punctuation">(</span>s <span class="token builtin">string</span><span class="token punctuation">)</span> <span class="token builtin">int</span> <span class="token punctuation">{</span>
	<span class="token comment">// state: f[i] &quot;前i&quot;个字符组成的子字符串需要最少几次cut(个数-1为索引)</span>
	<span class="token comment">// function: f[i] = MIN{f[j]+1}, j &lt; i &amp;&amp; [j+1 ~ i]这一段是一个回文串</span>
	<span class="token comment">// intialize: f[i] = i - 1 (f[0] = -1)</span>
	<span class="token comment">// answer: f[s.length()]</span>
	<span class="token keyword">if</span> <span class="token function">len</span><span class="token punctuation">(</span>s<span class="token punctuation">)</span> <span class="token operator">==</span> <span class="token number">0</span> <span class="token operator">||</span> <span class="token function">len</span><span class="token punctuation">(</span>s<span class="token punctuation">)</span> <span class="token operator">==</span> <span class="token number">1</span> <span class="token punctuation">{</span>
		<span class="token keyword">return</span> <span class="token number">0</span>
	<span class="token punctuation">}</span>
	f <span class="token operator">:=</span> <span class="token function">make</span><span class="token punctuation">(</span><span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token builtin">int</span><span class="token punctuation">,</span> <span class="token function">len</span><span class="token punctuation">(</span>s<span class="token punctuation">)</span><span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">)</span>
	f<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token operator">-</span><span class="token number">1</span>
	f<span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token number">0</span>
	<span class="token keyword">for</span> i <span class="token operator">:=</span> <span class="token number">1</span><span class="token punctuation">;</span> i <span class="token operator">&lt;=</span> <span class="token function">len</span><span class="token punctuation">(</span>s<span class="token punctuation">)</span><span class="token punctuation">;</span> i<span class="token operator">++</span> <span class="token punctuation">{</span>
		f<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> i <span class="token operator">-</span> <span class="token number">1</span>
		<span class="token keyword">for</span> j <span class="token operator">:=</span> <span class="token number">0</span><span class="token punctuation">;</span> j <span class="token operator">&lt;</span> i<span class="token punctuation">;</span> j<span class="token operator">++</span> <span class="token punctuation">{</span>
			<span class="token keyword">if</span> <span class="token function">isPalindrome</span><span class="token punctuation">(</span>s<span class="token punctuation">,</span> j<span class="token punctuation">,</span> i<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
				f<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token function">min</span><span class="token punctuation">(</span>f<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">,</span> f<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">)</span>
			<span class="token punctuation">}</span>
		<span class="token punctuation">}</span>
	<span class="token punctuation">}</span>
	<span class="token keyword">return</span> f<span class="token punctuation">[</span><span class="token function">len</span><span class="token punctuation">(</span>s<span class="token punctuation">)</span><span class="token punctuation">]</span>
<span class="token punctuation">}</span>
<span class="token keyword">func</span> <span class="token function">min</span><span class="token punctuation">(</span>a<span class="token punctuation">,</span> b <span class="token builtin">int</span><span class="token punctuation">)</span> <span class="token builtin">int</span> <span class="token punctuation">{</span>
	<span class="token keyword">if</span> a <span class="token operator">&gt;</span> b <span class="token punctuation">{</span>
		<span class="token keyword">return</span> b
	<span class="token punctuation">}</span>
	<span class="token keyword">return</span> a
<span class="token punctuation">}</span>
<span class="token keyword">func</span> <span class="token function">isPalindrome</span><span class="token punctuation">(</span>s <span class="token builtin">string</span><span class="token punctuation">,</span> i<span class="token punctuation">,</span> j <span class="token builtin">int</span><span class="token punctuation">)</span> <span class="token builtin">bool</span> <span class="token punctuation">{</span>
	<span class="token keyword">for</span> i <span class="token operator">&lt;</span> j <span class="token punctuation">{</span>
		<span class="token keyword">if</span> s<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">!=</span> s<span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token punctuation">{</span>
			<span class="token keyword">return</span> <span class="token boolean">false</span>
		<span class="token punctuation">}</span>
		i<span class="token operator">++</span>
		j<span class="token operator">--</span>
	<span class="token punctuation">}</span>
	<span class="token keyword">return</span> <span class="token boolean">true</span>
<span class="token punctuation">}</span>
</code></pre></div><p>注意点</p> <ul><li>判断回文字符串时，可以提前用动态规划算好，减少时间复杂度</li></ul> <h3 id="longest-increasing-subsequence"><a href="#longest-increasing-subsequence" class="header-anchor">#</a> <a href="https://leetcode-cn.com/problems/longest-increasing-subsequence/" target="_blank" rel="noopener noreferrer">longest-increasing-subsequence<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></h3> <blockquote><p>给定一个无序的整数数组，找到其中最长上升子序列的长度。</p></blockquote> <div class="language-go extra-class"><pre class="language-go"><code><span class="token keyword">func</span> <span class="token function">lengthOfLIS</span><span class="token punctuation">(</span>nums <span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token builtin">int</span><span class="token punctuation">)</span> <span class="token builtin">int</span> <span class="token punctuation">{</span>
    <span class="token comment">// f[i] 表示从0开始到i结尾的最长序列长度</span>
    <span class="token comment">// f[i] = max(f[j])+1 ,a[j]&lt;a[i]</span>
    <span class="token comment">// f[0...n-1] = 1</span>
    <span class="token comment">// max(f[0]...f[n-1])</span>
    <span class="token keyword">if</span> <span class="token function">len</span><span class="token punctuation">(</span>nums<span class="token punctuation">)</span> <span class="token operator">==</span> <span class="token number">0</span> <span class="token operator">||</span> <span class="token function">len</span><span class="token punctuation">(</span>nums<span class="token punctuation">)</span> <span class="token operator">==</span> <span class="token number">1</span> <span class="token punctuation">{</span>
        <span class="token keyword">return</span> <span class="token function">len</span><span class="token punctuation">(</span>nums<span class="token punctuation">)</span>
    <span class="token punctuation">}</span>
    f <span class="token operator">:=</span> <span class="token function">make</span><span class="token punctuation">(</span><span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token builtin">int</span><span class="token punctuation">,</span> <span class="token function">len</span><span class="token punctuation">(</span>nums<span class="token punctuation">)</span><span class="token punctuation">)</span>
    f<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token number">1</span>
    <span class="token keyword">for</span> i <span class="token operator">:=</span> <span class="token number">1</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> <span class="token function">len</span><span class="token punctuation">(</span>nums<span class="token punctuation">)</span><span class="token punctuation">;</span> i<span class="token operator">++</span> <span class="token punctuation">{</span>
        f<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token number">1</span>
        <span class="token keyword">for</span> j <span class="token operator">:=</span> <span class="token number">0</span><span class="token punctuation">;</span> j <span class="token operator">&lt;</span> i<span class="token punctuation">;</span> j<span class="token operator">++</span> <span class="token punctuation">{</span>
            <span class="token keyword">if</span> nums<span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">&lt;</span> nums<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token punctuation">{</span>
                f<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token function">max</span><span class="token punctuation">(</span>f<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">,</span> f<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">)</span>
            <span class="token punctuation">}</span>
        <span class="token punctuation">}</span>
    <span class="token punctuation">}</span>
    result <span class="token operator">:=</span> f<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span>
    <span class="token keyword">for</span> i <span class="token operator">:=</span> <span class="token number">1</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> <span class="token function">len</span><span class="token punctuation">(</span>nums<span class="token punctuation">)</span><span class="token punctuation">;</span> i<span class="token operator">++</span> <span class="token punctuation">{</span>
        result <span class="token operator">=</span> <span class="token function">max</span><span class="token punctuation">(</span>result<span class="token punctuation">,</span> f<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span>
    <span class="token punctuation">}</span>
    <span class="token keyword">return</span> result

<span class="token punctuation">}</span>
<span class="token keyword">func</span> <span class="token function">max</span><span class="token punctuation">(</span>a<span class="token punctuation">,</span> b <span class="token builtin">int</span><span class="token punctuation">)</span> <span class="token builtin">int</span> <span class="token punctuation">{</span>
    <span class="token keyword">if</span> a <span class="token operator">&gt;</span> b <span class="token punctuation">{</span>
        <span class="token keyword">return</span> a
    <span class="token punctuation">}</span>
    <span class="token keyword">return</span> b
<span class="token punctuation">}</span>
</code></pre></div><h3 id="word-break"><a href="#word-break" class="header-anchor">#</a> <a href="https://leetcode-cn.com/problems/word-break/" target="_blank" rel="noopener noreferrer">word-break<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></h3> <blockquote><p>给定一个<strong>非空</strong>字符串  <em>s</em>  和一个包含<strong>非空</strong>单词列表的字典  <em>wordDict</em>，判定  <em>s</em>  是否可以被空格拆分为一个或多个在字典中出现的单词。</p></blockquote> <div class="language-go extra-class"><pre class="language-go"><code><span class="token keyword">func</span> <span class="token function">wordBreak</span><span class="token punctuation">(</span>s <span class="token builtin">string</span><span class="token punctuation">,</span> wordDict <span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token builtin">string</span><span class="token punctuation">)</span> <span class="token builtin">bool</span> <span class="token punctuation">{</span>
	<span class="token comment">// f[i] 表示前i个字符是否可以被切分</span>
	<span class="token comment">// f[i] = f[j] &amp;&amp; s[j+1~i] in wordDict</span>
	<span class="token comment">// f[0] = true</span>
	<span class="token comment">// return f[len]</span>

	<span class="token keyword">if</span> <span class="token function">len</span><span class="token punctuation">(</span>s<span class="token punctuation">)</span> <span class="token operator">==</span> <span class="token number">0</span> <span class="token punctuation">{</span>
		<span class="token keyword">return</span> <span class="token boolean">true</span>
	<span class="token punctuation">}</span>
	f <span class="token operator">:=</span> <span class="token function">make</span><span class="token punctuation">(</span><span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token builtin">bool</span><span class="token punctuation">,</span> <span class="token function">len</span><span class="token punctuation">(</span>s<span class="token punctuation">)</span><span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">)</span>
	f<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token boolean">true</span>
	max <span class="token operator">:=</span> <span class="token function">maxLen</span><span class="token punctuation">(</span>wordDict<span class="token punctuation">)</span>
	<span class="token keyword">for</span> i <span class="token operator">:=</span> <span class="token number">1</span><span class="token punctuation">;</span> i <span class="token operator">&lt;=</span> <span class="token function">len</span><span class="token punctuation">(</span>s<span class="token punctuation">)</span><span class="token punctuation">;</span> i<span class="token operator">++</span> <span class="token punctuation">{</span>
		<span class="token keyword">for</span> j <span class="token operator">:=</span> i <span class="token operator">-</span> max<span class="token punctuation">;</span> j <span class="token operator">&lt;</span> i <span class="token operator">&amp;&amp;</span> j <span class="token operator">&gt;=</span> <span class="token number">0</span><span class="token punctuation">;</span> j<span class="token operator">++</span> <span class="token punctuation">{</span>
			<span class="token keyword">if</span> f<span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">&amp;&amp;</span> <span class="token function">inDict</span><span class="token punctuation">(</span>s<span class="token punctuation">[</span>j<span class="token punctuation">:</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
				f<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token boolean">true</span>
				<span class="token keyword">break</span>
			<span class="token punctuation">}</span>
		<span class="token punctuation">}</span>
	<span class="token punctuation">}</span>
	<span class="token keyword">return</span> f<span class="token punctuation">[</span><span class="token function">len</span><span class="token punctuation">(</span>s<span class="token punctuation">)</span><span class="token punctuation">]</span>
<span class="token punctuation">}</span>

<span class="token keyword">var</span> dict <span class="token operator">=</span> <span class="token function">make</span><span class="token punctuation">(</span><span class="token keyword">map</span><span class="token punctuation">[</span><span class="token builtin">string</span><span class="token punctuation">]</span><span class="token builtin">bool</span><span class="token punctuation">)</span>

<span class="token keyword">func</span> <span class="token function">maxLen</span><span class="token punctuation">(</span>wordDict <span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token builtin">string</span><span class="token punctuation">)</span> <span class="token builtin">int</span> <span class="token punctuation">{</span>
	max <span class="token operator">:=</span> <span class="token number">0</span>
	<span class="token keyword">for</span> <span class="token boolean">_</span><span class="token punctuation">,</span> v <span class="token operator">:=</span> <span class="token keyword">range</span> wordDict <span class="token punctuation">{</span>
		dict<span class="token punctuation">[</span>v<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token boolean">true</span>
		<span class="token keyword">if</span> <span class="token function">len</span><span class="token punctuation">(</span>v<span class="token punctuation">)</span> <span class="token operator">&gt;</span> max <span class="token punctuation">{</span>
			max <span class="token operator">=</span> <span class="token function">len</span><span class="token punctuation">(</span>v<span class="token punctuation">)</span>
		<span class="token punctuation">}</span>
	<span class="token punctuation">}</span>
	<span class="token keyword">return</span> max
<span class="token punctuation">}</span>

<span class="token keyword">func</span> <span class="token function">inDict</span><span class="token punctuation">(</span>s <span class="token builtin">string</span><span class="token punctuation">)</span> <span class="token builtin">bool</span> <span class="token punctuation">{</span>
	<span class="token boolean">_</span><span class="token punctuation">,</span> ok <span class="token operator">:=</span> dict<span class="token punctuation">[</span>s<span class="token punctuation">]</span>
	<span class="token keyword">return</span> ok
<span class="token punctuation">}</span>

</code></pre></div><p>小结</p> <p>常见处理方式是给 0 位置占位，这样处理问题时一视同仁，初始化则在原来基础上 length+1，返回结果 f[n]</p> <ul><li>状态可以为前 i 个</li> <li>初始化 length+1</li> <li>取值 index=i-1</li> <li>返回值：f[n]或者 f[m][n]</li></ul> <h2 id="two-sequences-dp（40-）"><a href="#two-sequences-dp（40-）" class="header-anchor">#</a> Two Sequences DP（40%）</h2> <h3 id="longest-common-subsequence"><a href="#longest-common-subsequence" class="header-anchor">#</a> <a href="https://leetcode-cn.com/problems/longest-common-subsequence/" target="_blank" rel="noopener noreferrer">longest-common-subsequence<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></h3> <blockquote><p>给定两个字符串  text1 和  text2，返回这两个字符串的最长公共子序列。
一个字符串的   子序列   是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，&quot;ace&quot; 是 &quot;abcde&quot; 的子序列，但 &quot;aec&quot; 不是 &quot;abcde&quot; 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。</p></blockquote> <div class="language-go extra-class"><pre class="language-go"><code><span class="token keyword">func</span> <span class="token function">longestCommonSubsequence</span><span class="token punctuation">(</span>a <span class="token builtin">string</span><span class="token punctuation">,</span> b <span class="token builtin">string</span><span class="token punctuation">)</span> <span class="token builtin">int</span> <span class="token punctuation">{</span>
    <span class="token comment">// dp[i][j] a前i个和b前j个字符最长公共子序列</span>
    <span class="token comment">// dp[m+1][n+1]</span>
    <span class="token comment">//   ' a d c e</span>
    <span class="token comment">// ' 0 0 0 0 0</span>
    <span class="token comment">// a 0 1 1 1 1</span>
    <span class="token comment">// c 0 1 1 2 1</span>
    <span class="token comment">//</span>
    dp<span class="token operator">:=</span><span class="token function">make</span><span class="token punctuation">(</span><span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token builtin">int</span><span class="token punctuation">,</span><span class="token function">len</span><span class="token punctuation">(</span>a<span class="token punctuation">)</span><span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">)</span>
    <span class="token keyword">for</span> i<span class="token operator">:=</span><span class="token number">0</span><span class="token punctuation">;</span>i<span class="token operator">&lt;=</span><span class="token function">len</span><span class="token punctuation">(</span>a<span class="token punctuation">)</span><span class="token punctuation">;</span>i<span class="token operator">++</span> <span class="token punctuation">{</span>
        dp<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">=</span><span class="token function">make</span><span class="token punctuation">(</span><span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token builtin">int</span><span class="token punctuation">,</span><span class="token function">len</span><span class="token punctuation">(</span>b<span class="token punctuation">)</span><span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">)</span>
    <span class="token punctuation">}</span>
    <span class="token keyword">for</span> i<span class="token operator">:=</span><span class="token number">1</span><span class="token punctuation">;</span>i<span class="token operator">&lt;=</span><span class="token function">len</span><span class="token punctuation">(</span>a<span class="token punctuation">)</span><span class="token punctuation">;</span>i<span class="token operator">++</span> <span class="token punctuation">{</span>
        <span class="token keyword">for</span> j<span class="token operator">:=</span><span class="token number">1</span><span class="token punctuation">;</span>j<span class="token operator">&lt;=</span><span class="token function">len</span><span class="token punctuation">(</span>b<span class="token punctuation">)</span><span class="token punctuation">;</span>j<span class="token operator">++</span> <span class="token punctuation">{</span>
            <span class="token comment">// 相等取左上元素+1，否则取左或上的较大值</span>
            <span class="token keyword">if</span> a<span class="token punctuation">[</span>i<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token operator">==</span>b<span class="token punctuation">[</span>j<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span> <span class="token punctuation">{</span>
                dp<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token operator">=</span>dp<span class="token punctuation">[</span>i<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token operator">+</span><span class="token number">1</span>
            <span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token punctuation">{</span>
                dp<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token operator">=</span><span class="token function">max</span><span class="token punctuation">(</span>dp<span class="token punctuation">[</span>i<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">,</span>dp<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">)</span>
            <span class="token punctuation">}</span>
        <span class="token punctuation">}</span>
    <span class="token punctuation">}</span>
    <span class="token keyword">return</span> dp<span class="token punctuation">[</span><span class="token function">len</span><span class="token punctuation">(</span>a<span class="token punctuation">)</span><span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token function">len</span><span class="token punctuation">(</span>b<span class="token punctuation">)</span><span class="token punctuation">]</span>
<span class="token punctuation">}</span>
<span class="token keyword">func</span> <span class="token function">max</span><span class="token punctuation">(</span>a<span class="token punctuation">,</span>b <span class="token builtin">int</span><span class="token punctuation">)</span><span class="token builtin">int</span> <span class="token punctuation">{</span>
    <span class="token keyword">if</span> a<span class="token operator">&gt;</span>b<span class="token punctuation">{</span>
        <span class="token keyword">return</span> a
    <span class="token punctuation">}</span>
    <span class="token keyword">return</span> b
<span class="token punctuation">}</span>
</code></pre></div><p>注意点</p> <ul><li>go 切片初始化</li></ul> <div class="language-go extra-class"><pre class="language-go"><code>dp<span class="token operator">:=</span><span class="token function">make</span><span class="token punctuation">(</span><span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token builtin">int</span><span class="token punctuation">,</span><span class="token function">len</span><span class="token punctuation">(</span>a<span class="token punctuation">)</span><span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">)</span>
<span class="token keyword">for</span> i<span class="token operator">:=</span><span class="token number">0</span><span class="token punctuation">;</span>i<span class="token operator">&lt;=</span><span class="token function">len</span><span class="token punctuation">(</span>a<span class="token punctuation">)</span><span class="token punctuation">;</span>i<span class="token operator">++</span> <span class="token punctuation">{</span>
    dp<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">=</span><span class="token function">make</span><span class="token punctuation">(</span><span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token builtin">int</span><span class="token punctuation">,</span><span class="token function">len</span><span class="token punctuation">(</span>b<span class="token punctuation">)</span><span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">)</span>
<span class="token punctuation">}</span>
</code></pre></div><ul><li>从 1 开始遍历到最大长度</li> <li>索引需要减一</li></ul> <h3 id="edit-distance"><a href="#edit-distance" class="header-anchor">#</a> <a href="https://leetcode-cn.com/problems/edit-distance/" target="_blank" rel="noopener noreferrer">edit-distance<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></h3> <blockquote><p>给你两个单词  word1 和  word2，请你计算出将  word1  转换成  word2 所使用的最少操作数  
你可以对一个单词进行如下三种操作：
插入一个字符
删除一个字符
替换一个字符</p></blockquote> <p>思路：和上题很类似，相等则不需要操作，否则取删除、插入、替换最小操作次数的值+1</p> <div class="language-go extra-class"><pre class="language-go"><code><span class="token keyword">func</span> <span class="token function">minDistance</span><span class="token punctuation">(</span>word1 <span class="token builtin">string</span><span class="token punctuation">,</span> word2 <span class="token builtin">string</span><span class="token punctuation">)</span> <span class="token builtin">int</span> <span class="token punctuation">{</span>
    <span class="token comment">// dp[i][j] 表示a字符串的前i个字符编辑为b字符串的前j个字符最少需要多少次操作</span>
    <span class="token comment">// dp[i][j] = OR(dp[i-1][j-1]，a[i]==b[j],min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1)</span>
    dp<span class="token operator">:=</span><span class="token function">make</span><span class="token punctuation">(</span><span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token builtin">int</span><span class="token punctuation">,</span><span class="token function">len</span><span class="token punctuation">(</span>word1<span class="token punctuation">)</span><span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">)</span>
    <span class="token keyword">for</span> i<span class="token operator">:=</span><span class="token number">0</span><span class="token punctuation">;</span>i<span class="token operator">&lt;</span><span class="token function">len</span><span class="token punctuation">(</span>dp<span class="token punctuation">)</span><span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">{</span>
        dp<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">=</span><span class="token function">make</span><span class="token punctuation">(</span><span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token builtin">int</span><span class="token punctuation">,</span><span class="token function">len</span><span class="token punctuation">(</span>word2<span class="token punctuation">)</span><span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">)</span>
    <span class="token punctuation">}</span>
    <span class="token keyword">for</span> i<span class="token operator">:=</span><span class="token number">0</span><span class="token punctuation">;</span>i<span class="token operator">&lt;</span><span class="token function">len</span><span class="token punctuation">(</span>dp<span class="token punctuation">)</span><span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">{</span>
        dp<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token operator">=</span>i
    <span class="token punctuation">}</span>
    <span class="token keyword">for</span> j<span class="token operator">:=</span><span class="token number">0</span><span class="token punctuation">;</span>j<span class="token operator">&lt;</span><span class="token function">len</span><span class="token punctuation">(</span>dp<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>j<span class="token operator">++</span><span class="token punctuation">{</span>
        dp<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token operator">=</span>j
    <span class="token punctuation">}</span>
    <span class="token keyword">for</span> i<span class="token operator">:=</span><span class="token number">1</span><span class="token punctuation">;</span>i<span class="token operator">&lt;=</span><span class="token function">len</span><span class="token punctuation">(</span>word1<span class="token punctuation">)</span><span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">{</span>
        <span class="token keyword">for</span> j<span class="token operator">:=</span><span class="token number">1</span><span class="token punctuation">;</span>j<span class="token operator">&lt;=</span><span class="token function">len</span><span class="token punctuation">(</span>word2<span class="token punctuation">)</span><span class="token punctuation">;</span>j<span class="token operator">++</span><span class="token punctuation">{</span>
            <span class="token comment">// 相等则不需要操作</span>
            <span class="token keyword">if</span> word1<span class="token punctuation">[</span>i<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token operator">==</span>word2<span class="token punctuation">[</span>j<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span> <span class="token punctuation">{</span>
                dp<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token operator">=</span>dp<span class="token punctuation">[</span>i<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span>
            <span class="token punctuation">}</span><span class="token keyword">else</span><span class="token punctuation">{</span> <span class="token comment">// 否则取删除、插入、替换最小操作次数的值+1</span>
                dp<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token operator">=</span><span class="token function">min</span><span class="token punctuation">(</span><span class="token function">min</span><span class="token punctuation">(</span>dp<span class="token punctuation">[</span>i<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">,</span>dp<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">,</span>dp<span class="token punctuation">[</span>i<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token operator">+</span><span class="token number">1</span>
            <span class="token punctuation">}</span>
        <span class="token punctuation">}</span>
    <span class="token punctuation">}</span>
    <span class="token keyword">return</span> dp<span class="token punctuation">[</span><span class="token function">len</span><span class="token punctuation">(</span>word1<span class="token punctuation">)</span><span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token function">len</span><span class="token punctuation">(</span>word2<span class="token punctuation">)</span><span class="token punctuation">]</span>
<span class="token punctuation">}</span>
<span class="token keyword">func</span> <span class="token function">min</span><span class="token punctuation">(</span>a<span class="token punctuation">,</span>b <span class="token builtin">int</span><span class="token punctuation">)</span><span class="token builtin">int</span><span class="token punctuation">{</span>
    <span class="token keyword">if</span> a<span class="token operator">&gt;</span>b<span class="token punctuation">{</span>
        <span class="token keyword">return</span> b
    <span class="token punctuation">}</span>
    <span class="token keyword">return</span> a
<span class="token punctuation">}</span>
</code></pre></div><p>说明</p> <blockquote><p>另外一种做法：MAXLEN(a,b)-LCS(a,b)</p></blockquote> <h2 id="零钱和背包（10-）"><a href="#零钱和背包（10-）" class="header-anchor">#</a> 零钱和背包（10%）</h2> <h3 id="coin-change"><a href="#coin-change" class="header-anchor">#</a> <a href="https://leetcode-cn.com/problems/coin-change/" target="_blank" rel="noopener noreferrer">coin-change<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></h3> <blockquote><p>给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回  -1。</p></blockquote> <p>思路：和其他 DP 不太一样，i 表示钱或者容量</p> <div class="language-go extra-class"><pre class="language-go"><code><span class="token keyword">func</span> <span class="token function">coinChange</span><span class="token punctuation">(</span>coins <span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token builtin">int</span><span class="token punctuation">,</span> amount <span class="token builtin">int</span><span class="token punctuation">)</span> <span class="token builtin">int</span> <span class="token punctuation">{</span>
    <span class="token comment">// 状态 dp[i]表示金额为i时，组成的最小硬币个数</span>
    <span class="token comment">// 推导 dp[i]  = min(dp[i-1], dp[i-2], dp[i-5])+1, 前提 i-coins[j] &gt; 0</span>
    <span class="token comment">// 初始化为最大值 dp[i]=amount+1</span>
    <span class="token comment">// 返回值 dp[n] or dp[n]&gt;amount =&gt;-1</span>
    dp<span class="token operator">:=</span><span class="token function">make</span><span class="token punctuation">(</span><span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token builtin">int</span><span class="token punctuation">,</span>amount<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">)</span>
    <span class="token keyword">for</span> i<span class="token operator">:=</span><span class="token number">0</span><span class="token punctuation">;</span>i<span class="token operator">&lt;=</span>amount<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">{</span>
        dp<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">=</span>amount<span class="token operator">+</span><span class="token number">1</span>
    <span class="token punctuation">}</span>
    dp<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token operator">=</span><span class="token number">0</span>
    <span class="token keyword">for</span> i<span class="token operator">:=</span><span class="token number">1</span><span class="token punctuation">;</span>i<span class="token operator">&lt;=</span>amount<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">{</span>
        <span class="token keyword">for</span> j<span class="token operator">:=</span><span class="token number">0</span><span class="token punctuation">;</span>j<span class="token operator">&lt;</span><span class="token function">len</span><span class="token punctuation">(</span>coins<span class="token punctuation">)</span><span class="token punctuation">;</span>j<span class="token operator">++</span><span class="token punctuation">{</span>
            <span class="token keyword">if</span>  i<span class="token operator">-</span>coins<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token operator">&gt;=</span><span class="token number">0</span>  <span class="token punctuation">{</span>
                dp<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">=</span><span class="token function">min</span><span class="token punctuation">(</span>dp<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">,</span>dp<span class="token punctuation">[</span>i<span class="token operator">-</span>coins<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">]</span><span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">)</span>
            <span class="token punctuation">}</span>
        <span class="token punctuation">}</span>
    <span class="token punctuation">}</span>
    <span class="token keyword">if</span> dp<span class="token punctuation">[</span>amount<span class="token punctuation">]</span> <span class="token operator">&gt;</span> amount <span class="token punctuation">{</span>
        <span class="token keyword">return</span> <span class="token operator">-</span><span class="token number">1</span>
    <span class="token punctuation">}</span>
    <span class="token keyword">return</span> dp<span class="token punctuation">[</span>amount<span class="token punctuation">]</span>

<span class="token punctuation">}</span>
<span class="token keyword">func</span> <span class="token function">min</span><span class="token punctuation">(</span>a<span class="token punctuation">,</span>b <span class="token builtin">int</span><span class="token punctuation">)</span><span class="token builtin">int</span><span class="token punctuation">{</span>
    <span class="token keyword">if</span> a<span class="token operator">&gt;</span>b<span class="token punctuation">{</span>
        <span class="token keyword">return</span> b
    <span class="token punctuation">}</span>
    <span class="token keyword">return</span> a
<span class="token punctuation">}</span>
</code></pre></div><p>注意</p> <blockquote><p>dp[i-a[j]] 决策 a[j]是否参与</p></blockquote> <h3 id="backpack"><a href="#backpack" class="header-anchor">#</a> <a href="https://www.lintcode.com/problem/backpack/description" target="_blank" rel="noopener noreferrer">backpack<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></h3> <blockquote><p>在 n 个物品中挑选若干物品装入背包，最多能装多满？假设背包的大小为 m，每个物品的大小为 A[i]</p></blockquote> <div class="language-go extra-class"><pre class="language-go"><code><span class="token keyword">func</span> backPack <span class="token punctuation">(</span>m <span class="token builtin">int</span><span class="token punctuation">,</span> A <span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token builtin">int</span><span class="token punctuation">)</span> <span class="token builtin">int</span> <span class="token punctuation">{</span>
    <span class="token comment">// write your code here</span>
    <span class="token comment">// f[i][j] 前i个物品，是否能装j</span>
    <span class="token comment">// f[i][j] =f[i-1][j] f[i-1][j-a[i] j&gt;a[i]</span>
    <span class="token comment">// f[0][0]=true f[...][0]=true</span>
    <span class="token comment">// f[n][X]</span>
    f<span class="token operator">:=</span><span class="token function">make</span><span class="token punctuation">(</span><span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token builtin">bool</span><span class="token punctuation">,</span><span class="token function">len</span><span class="token punctuation">(</span>A<span class="token punctuation">)</span><span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">)</span>
    <span class="token keyword">for</span> i<span class="token operator">:=</span><span class="token number">0</span><span class="token punctuation">;</span>i<span class="token operator">&lt;=</span><span class="token function">len</span><span class="token punctuation">(</span>A<span class="token punctuation">)</span><span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">{</span>
        f<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">=</span><span class="token function">make</span><span class="token punctuation">(</span><span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token builtin">bool</span><span class="token punctuation">,</span>m<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">)</span>
    <span class="token punctuation">}</span>
    f<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token operator">=</span><span class="token boolean">true</span>
    <span class="token keyword">for</span> i<span class="token operator">:=</span><span class="token number">1</span><span class="token punctuation">;</span>i<span class="token operator">&lt;=</span><span class="token function">len</span><span class="token punctuation">(</span>A<span class="token punctuation">)</span><span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">{</span>
        <span class="token keyword">for</span> j<span class="token operator">:=</span><span class="token number">0</span><span class="token punctuation">;</span>j<span class="token operator">&lt;=</span>m<span class="token punctuation">;</span>j<span class="token operator">++</span><span class="token punctuation">{</span>
            f<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token operator">=</span>f<span class="token punctuation">[</span>i<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span>
            <span class="token keyword">if</span> j<span class="token operator">-</span>A<span class="token punctuation">[</span>i<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token operator">&gt;=</span><span class="token number">0</span> <span class="token operator">&amp;&amp;</span> f<span class="token punctuation">[</span>i<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token operator">-</span>A<span class="token punctuation">[</span>i<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">]</span><span class="token punctuation">{</span>
                f<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token operator">=</span><span class="token boolean">true</span>
            <span class="token punctuation">}</span>
        <span class="token punctuation">}</span>
    <span class="token punctuation">}</span>
    <span class="token keyword">for</span> i<span class="token operator">:=</span>m<span class="token punctuation">;</span>i<span class="token operator">&gt;=</span><span class="token number">0</span><span class="token punctuation">;</span>i<span class="token operator">--</span><span class="token punctuation">{</span>
        <span class="token keyword">if</span> f<span class="token punctuation">[</span><span class="token function">len</span><span class="token punctuation">(</span>A<span class="token punctuation">)</span><span class="token punctuation">]</span><span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token punctuation">{</span>
            <span class="token keyword">return</span> i
        <span class="token punctuation">}</span>
    <span class="token punctuation">}</span>
    <span class="token keyword">return</span> <span class="token number">0</span>
<span class="token punctuation">}</span>

</code></pre></div><h3 id="backpack-ii"><a href="#backpack-ii" class="header-anchor">#</a> <a href="https://www.lintcode.com/problem/backpack-ii/description" target="_blank" rel="noopener noreferrer">backpack-ii<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></h3> <blockquote><p>有 <code>n</code> 个物品和一个大小为 <code>m</code> 的背包. 给定数组 <code>A</code> 表示每个物品的大小和数组 <code>V</code> 表示每个物品的价值.
问最多能装入背包的总价值是多大?</p></blockquote> <p>思路：f[i][j] 前 i 个物品，装入 j 背包 最大价值</p> <div class="language-go extra-class"><pre class="language-go"><code><span class="token keyword">func</span> backPackII <span class="token punctuation">(</span>m <span class="token builtin">int</span><span class="token punctuation">,</span> A <span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token builtin">int</span><span class="token punctuation">,</span> V <span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token builtin">int</span><span class="token punctuation">)</span> <span class="token builtin">int</span> <span class="token punctuation">{</span>
    <span class="token comment">// write your code here</span>
    <span class="token comment">// f[i][j] 前i个物品，装入j背包 最大价值</span>
    <span class="token comment">// f[i][j] =max(f[i-1][j] ,f[i-1][j-A[i]]+V[i]) 是否加入A[i]物品</span>
    <span class="token comment">// f[0][0]=0 f[0][...]=0 f[...][0]=0</span>
    f<span class="token operator">:=</span><span class="token function">make</span><span class="token punctuation">(</span><span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token builtin">int</span><span class="token punctuation">,</span><span class="token function">len</span><span class="token punctuation">(</span>A<span class="token punctuation">)</span><span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">)</span>
    <span class="token keyword">for</span> i<span class="token operator">:=</span><span class="token number">0</span><span class="token punctuation">;</span>i<span class="token operator">&lt;</span><span class="token function">len</span><span class="token punctuation">(</span>A<span class="token punctuation">)</span><span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">{</span>
        f<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">=</span><span class="token function">make</span><span class="token punctuation">(</span><span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token builtin">int</span><span class="token punctuation">,</span>m<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">)</span>
    <span class="token punctuation">}</span>
    <span class="token keyword">for</span> i<span class="token operator">:=</span><span class="token number">1</span><span class="token punctuation">;</span>i<span class="token operator">&lt;=</span><span class="token function">len</span><span class="token punctuation">(</span>A<span class="token punctuation">)</span><span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">{</span>
        <span class="token keyword">for</span> j<span class="token operator">:=</span><span class="token number">0</span><span class="token punctuation">;</span>j<span class="token operator">&lt;=</span>m<span class="token punctuation">;</span>j<span class="token operator">++</span><span class="token punctuation">{</span>
            f<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token operator">=</span>f<span class="token punctuation">[</span>i<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span>
            <span class="token keyword">if</span> j<span class="token operator">-</span>A<span class="token punctuation">[</span>i<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span> <span class="token operator">&gt;=</span> <span class="token number">0</span><span class="token punctuation">{</span>
                f<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token operator">=</span><span class="token function">max</span><span class="token punctuation">(</span>f<span class="token punctuation">[</span>i<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">,</span>f<span class="token punctuation">[</span>i<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token operator">-</span>A<span class="token punctuation">[</span>i<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">]</span><span class="token operator">+</span>V<span class="token punctuation">[</span>i<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">)</span>
            <span class="token punctuation">}</span>
        <span class="token punctuation">}</span>
    <span class="token punctuation">}</span>
    <span class="token keyword">return</span> f<span class="token punctuation">[</span><span class="token function">len</span><span class="token punctuation">(</span>A<span class="token punctuation">)</span><span class="token punctuation">]</span><span class="token punctuation">[</span>m<span class="token punctuation">]</span>
<span class="token punctuation">}</span>
<span class="token keyword">func</span> <span class="token function">max</span><span class="token punctuation">(</span>a<span class="token punctuation">,</span>b <span class="token builtin">int</span><span class="token punctuation">)</span><span class="token builtin">int</span><span class="token punctuation">{</span>
    <span class="token keyword">if</span> a<span class="token operator">&gt;</span>b<span class="token punctuation">{</span>
        <span class="token keyword">return</span> a
    <span class="token punctuation">}</span>
    <span class="token keyword">return</span> b
<span class="token punctuation">}</span>
</code></pre></div><h2 id="练习"><a href="#练习" class="header-anchor">#</a> 练习</h2> <p>Matrix DP (10%)</p> <ul><li>[ ] <a href="https://leetcode-cn.com/problems/triangle/" target="_blank" rel="noopener noreferrer">triangle<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></li> <li>[ ] <a href="https://leetcode-cn.com/problems/minimum-path-sum/" target="_blank" rel="noopener noreferrer">minimum-path-sum<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></li> <li>[ ] <a href="https://leetcode-cn.com/problems/unique-paths/" target="_blank" rel="noopener noreferrer">unique-paths<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></li> <li>[ ] <a href="https://leetcode-cn.com/problems/unique-paths-ii/" target="_blank" rel="noopener noreferrer">unique-paths-ii<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></li></ul> <p>Sequence (40%)</p> <ul><li>[ ] <a href="https://leetcode-cn.com/problems/climbing-stairs/" target="_blank" rel="noopener noreferrer">climbing-stairs<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></li> <li>[ ] <a href="https://leetcode-cn.com/problems/jump-game/" target="_blank" rel="noopener noreferrer">jump-game<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></li> <li>[ ] <a href="https://leetcode-cn.com/problems/jump-game-ii/" target="_blank" rel="noopener noreferrer">jump-game-ii<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></li> <li>[ ] <a href="https://leetcode-cn.com/problems/palindrome-partitioning-ii/" target="_blank" rel="noopener noreferrer">palindrome-partitioning-ii<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></li> <li>[ ] <a href="https://leetcode-cn.com/problems/longest-increasing-subsequence/" target="_blank" rel="noopener noreferrer">longest-increasing-subsequence<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></li> <li>[ ] <a href="https://leetcode-cn.com/problems/word-break/" target="_blank" rel="noopener noreferrer">word-break<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></li></ul> <p>Two Sequences DP (40%)</p> <ul><li>[ ] <a href="https://leetcode-cn.com/problems/longest-common-subsequence/" target="_blank" rel="noopener noreferrer">longest-common-subsequence<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></li> <li>[ ] <a href="https://leetcode-cn.com/problems/edit-distance/" target="_blank" rel="noopener noreferrer">edit-distance<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></li></ul> <p>Backpack &amp; Coin Change (10%)</p> <ul><li>[ ] <a href="https://leetcode-cn.com/problems/coin-change/" target="_blank" rel="noopener noreferrer">coin-change<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></li> <li>[ ] <a href="https://www.lintcode.com/problem/backpack/description" target="_blank" rel="noopener noreferrer">backpack<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></li> <li>[ ] <a href="https://www.lintcode.com/problem/backpack-ii/description" target="_blank" rel="noopener noreferrer">backpack-ii<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></li></ul></div> <footer class="page-edit"><!----> <div class="last-updated"><span class="prefix">上次更新:</span> <span class="time">9/23/2020, 8:44:45 AM</span></div></footer> <!----> </main></div><div class="global-ui"></div></div>
    <script src="/assets/js/app.cb35c8f6.js" defer></script><script src="/assets/js/2.063846a6.js" defer></script><script src="/assets/js/4.1ffb4609.js" defer></script><script src="/assets/js/575.b0d429a1.js" defer></script>
  </body>
</html>
